On Feb 15, Artur Biesiadowski wrote:
> HashMap uses array of Bucket objects, which in turn are just wrappers
> around pointer to Node instance. If I understand this scheme correctly,
> than for every object put into list, both Bucket instance and Node
> instance is created, with additional Node for every conflicting
> hashcode.
>
> Would not it be better to use directly array of Nodes ? Saving
> allocation of one object for each value put in should be a major benefit
> both in performance and memory for HashMap/Hashtable (and sets which are
> based on this classes).
>
> If nobody have anything against the idea, I'll try to implement the
> change.
I already tried this a few days ago. I have used a linear collision
resolution strategy, since that allows complete removing. I also
tried a double hash strategy. The files are now at
http://www.informatik.uni-oldenburg.de/~delwi/classpath/HashMap
There is also a small ad hoc benchmark. IIRC some operations were
notably faster than the normal hashcode, the others were about the
same speed. Another advantage is, that the iteration over the hash
map gets _much_ simpler.
I think it would be wise, to implement HashSet in a similar way, but
separately, since this is much more space efficient (the value array
can be omitted).
Feel free to play with these classes if you have some ideas.
Jochen
