F
Frank Cisco
What determines the ordering of an unsorted hashtable?
L
Lothar Kimmeringer
Frank said:
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:
And, within a hash chain, the order in which the key was added.
R
Roedy Green
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)
T
Tom Anderson
The entrails of geese.
tom
L
Lothar Kimmeringer
Mike said:
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:
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 Hashtable, too.
Was there a reason to think otherwise?
L
Lothar Kimmeringer
Lew said:
Not all the time.
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:
"ISAM" files?
L
Lew
Eric Sosman said:
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:
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
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
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:
It's a standard acronym and Roedy naturally assumed that most people here
would be familiar with it.
M
Mike Schilling
Lew 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.
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
R
Roedy Green
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
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)