Hashtable ordering

L

Lothar Kimmeringer

Frank said:
What determines the ordering of an unsorted hashtable?

AFAIR the hashcode of the key modulo the size of the internal
array, the Map.Entry-instances are stored in.


Regards, Lothar
--
Lothar Kimmeringer E-Mail: (e-mail address removed)
PGP-encrypted mails preferred (Key-ID: 0x8BC3CD81)

Always remember: The answer is forty-two, there can only be wrong
questions!
 
M

Mike Schilling

Lothar said:
AFAIR the hashcode of the key modulo the size of the internal
array, the Map.Entry-instances are stored in.

And, within a hash chain, the order in which the key was added.
 
R

Roedy Green

What determines the ordering of an unsorted hashtable?

Determinate, but random. The order has no useful meaning. To see how
it works, look at the source code for Hashtable or HashMap. One of the
very first programs I ever wrote was a Hashtable lookup in FORTRAN. To
me the algorithm was magical, a true almost-free lunch. I still recall
choosing 149 as my prime. Oddly, until Java, many programmers were
unaware of it. They would use external ISAM files when a small
ram-resident HashMap would work much faster.

If you want the Iterator to produce results in entry-add order, use
LinkedHashMap instead of HashMap.

See http://mindprod.com/jgloss/hashtable.html
http://mindprod.com/jgloss/hashmap.html

--
Roedy Green Canadian Mind Products
http://mindprod.com

"There is an evil which ought to be guarded against, in the indefinite accumulation of property,
from the capacity of holding it in perpetuity by... corporations.
The power of all corporations aught to be limited in this respect.
The growing wealth acquired by them never fails to be a source of abuses."
~ James Madison (born: 1751-03-16 died: 1836-06-28 at age: 85)
 
L

Lothar Kimmeringer

Mike said:
And, within a hash chain, the order in which the key was added.

That's the implementation of HashMap. Possible that they changed
the internal logic of Hashtable as well when introducing HashMap,
but I'm not 100% sure (and too lazy to check now ;-)


Regards, Lothar
--
Lothar Kimmeringer E-Mail: (e-mail address removed)
PGP-encrypted mails preferred (Key-ID: 0x8BC3CD81)

Always remember: The answer is forty-two, there can only be wrong
questions!
 
L

Lothar Kimmeringer

Roedy said:
Oddly, until Java, many programmers were
unaware of it. They would use external ISAM files when a small
ram-resident HashMap would work much faster.

s/Java/Perl/


Regards, Lothar
--
Lothar Kimmeringer E-Mail: (e-mail address removed)
PGP-encrypted mails preferred (Key-ID: 0x8BC3CD81)

Always remember: The answer is forty-two, there can only be wrong
questions!
 
L

Lew

That's the implementation of HashMap. Possible that they changed
the internal logic of Hashtable as well when introducing HashMap,
but I'm not 100% sure (and too lazy to check now ;-)

That's the implementation of Hashtable, too.

Was there a reason to think otherwise?
 
L

Lothar Kimmeringer

Lew said:
That's the implementation of Hashtable, too.

Not all the time.
Was there a reason to think otherwise?

The fact that the implementation was different in Java 1.0 and 1.1
I was reading the sources at that time and there was a rehash
every time when there was a collision.


Regards, Lothar
--
Lothar Kimmeringer E-Mail: (e-mail address removed)
PGP-encrypted mails preferred (Key-ID: 0x8BC3CD81)

Always remember: The answer is forty-two, there can only be wrong
questions!
 
D

Dave Searles

Roedy said:
Determinate, but random. The order has no useful meaning. To see how
it works, look at the source code for Hashtable or HashMap. One of the
very first programs I ever wrote was a Hashtable lookup in FORTRAN. To
me the algorithm was magical, a true almost-free lunch. I still recall
choosing 149 as my prime. Oddly, until Java, many programmers were
unaware of it. They would use external ISAM files when a small
ram-resident HashMap would work much faster.

"ISAM" files?
 
L

Lew

Eric Sosman said:
... In short, the answer to the question you asked is "Yes."

All right, there's reason to believe that the implementation of
Hashtable is different from what Lothar and others said, but not
different from HashMap's, with respect to hashing and bucket lists.

I'm not at all concerned about implementations that predate Java 2.
Any conclusions about Java drawn on such old versions are suspect.
 
D

Dave Searles

Eric said:
It's an acronym: Igoogle Sit Afor Myourself.

You've missed the point, which was that Roedy failed to communicate
clearly by not expanding its first use in his post.
 
R

Roedy Green

"ISAM" files?

This was IBM's Indexed Sequential file Access Method for OS-360. It
probably still lives, eventually replaced by VSAM. You would look up
a record by key. It was notorious for its poor performance on insert.
You had to rebuild them frequently.

Programmers prior to Java often referred to any sort of keyed file
access method (Disk-based Treemap) as ISAM. I wrote one myself, a high
performance Btree for the PDP-11 for real time use.
--
Roedy Green Canadian Mind Products
http://mindprod.com

"There is an evil which ought to be guarded against, in the indefinite accumulation of property,
from the capacity of holding it in perpetuity by... corporations.
The power of all corporations aught to be limited in this respect.
The growing wealth acquired by them never fails to be a source of abuses."
~ James Madison (born: 1751-03-16 died: 1836-06-28 at age: 85)
 
M

Martin Gregorie

Oddly, until Java, many programmers were unaware of it.
They would use external ISAM files when a small ram-resident HashMap
would work much faster.
You're right about hashing, but in COBOL anyway, SEARCH could use a
binary chop to search DATA DIVISION tables. The only problem was that
Codasyl never thought of extending SORT to work with tables, so some of
us got quite good at writing efficient replacement sorts - the
programmers ordinaire persisted in using bubble sorts and/or the
sequential scan form of SEARCH.
 
L

Lew

Dave said:
You've missed the point, which was that Roedy failed to communicate
clearly by not expanding its first use in his post.

It's a standard acronym and Roedy naturally assumed that most people here
would be familiar with it.
 
M

Mike Schilling

Lew said:
It's a standard acronym and Roedy naturally assumed that most people
here would be familiar with it.

People for whom COBOL and mainframes are mythical beasts from bygone ages
might well not have heard of it. You're showing your age, Lew :)

Of course, anyone who, on seeing an unfamiliar term in a technical
newsgroup, complains instead of Googling has an inflated view of his own
omniscience.
 
D

Dave Searles

Mike said:
People for whom COBOL and mainframes are mythical beasts from bygone ages
might well not have heard of it. You're showing your age, Lew :)

Of course, anyone who, on seeing an unfamiliar term in a technical
newsgroup, complains instead of Googling has an inflated view of his own
omniscience.

Or has another reason for posting than just to find out the answer, such
as to remind the previous poster that not everyone is familiar with the
acronym they just used. In particular, that it is NOT a "standard"
acronym, as in a common textism or email-ism like LOL, or one you'd find
in the news.answers.newusers FAQ, or one that would be known to
practitioners in the field -- in a Java newsgroup, that's things like
JNI and other Java-specific things, and things like RAM and HDD that are
general technical computer-isms. COBOLisms would be expected to be known
in comp.lang.cobol, if there is such a newsgroup, but not in comp.lang.java.
 
L

Lew

Dave said:
Or has another reason for posting than just to find out the answer, such
as to remind the previous poster that not everyone is familiar with the
acronym they just used. In particular, that it is NOT a "standard"
acronym, as in a common textism or email-ism like LOL, or one you'd find
in the news.answers.newusers FAQ, or one that would be known to
practitioners in the field -- in a Java newsgroup, that's things like
JNI and other Java-specific things, and things like RAM and HDD that are
general technical computer-isms. COBOLisms would be expected to be known
in comp.lang.cobol, if there is such a newsgroup, but not in
comp.lang.java.

OK, fine:
<http://www.google.com/#q=ISAM>
 
R

Roedy Green

I'm not at all concerned about implementations that predate Java 2.
Any conclusions about Java drawn on such old versions are suspect.

Most of use do our poking around in the source code when a feature
first becomes available. We don't bother going back to see if
anything has changed unless the API changes, which rarely happens. It
is thus fairly easy for information to go stale.

"Knowledge keeps no better than fish."
~ Alfred North Whitehead


--
Roedy Green Canadian Mind Products
http://mindprod.com

"There is an evil which ought to be guarded against, in the indefinite accumulation of property,
from the capacity of holding it in perpetuity by... corporations.
The power of all corporations aught to be limited in this respect.
The growing wealth acquired by them never fails to be a source of abuses."
~ James Madison (born: 1751-03-16 died: 1836-06-28 at age: 85)
 
R

Roedy Green

You've missed the point, which was that Roedy failed to communicate
clearly by not expanding its first use in his post.

If every programmer of your own generation knows what a word means, it
is not obvious you need to provide footnotes.

Other such historical words that might need footnotes:
Hollerith
punch card
paper tape
mag tape
core
tube
CRT
TTY
Univac
Xerox (as a mainframe company)
Control Data
Ahmdahl
data cell
merge
collator
control break
RPG
engine
COBOL
FORTRAN
Algol
Basic
TSO
time sharing
IBM 360/370
IBM OS 370/MVS
MTS
pen plotter
line printer
dropping a card tray
Oak
JavaOS
PicoJava
GPSS


--
Roedy Green Canadian Mind Products
http://mindprod.com

"There is an evil which ought to be guarded against, in the indefinite accumulation of property,
from the capacity of holding it in perpetuity by... corporations.
The power of all corporations aught to be limited in this respect.
The growing wealth acquired by them never fails to be a source of abuses."
~ James Madison (born: 1751-03-16 died: 1836-06-28 at age: 85)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top