Which of Java's hash structures supports 'linear chaining'?

Question

For homework, I have to implement a variety of hash functions in C++ or Java. I'm comfortable working with Java, but haven't used its hash functionality.

I want a hash structure that links colliding keys. Like this:

enter image description here

Is LinkedHashMap the correct choice here? Is it HashMap? Either? Why?

AFAIK, none does. LinkedHashMap uses a linked list to store the insertion order, not for linear chaining. — helpermethod, Apr 08 '11 at 13:00
@omgzor: try with hashtable , where u can get collision. as hashmap has enhanced hash function which prevent keys falling to same bucket.read this link http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java#HashMap.hash%28int%29 — Dead Programmer, Apr 08 '11 at 13:13
If this is homework, then supposedly your task here is to create such a structure yourself, not to simply use an existing one. — Paŭlo Ebermann, Apr 08 '11 at 14:08
@Suresh: the private method `hash()` does not have the reason to avoid keys falling in the same bucket, it simply does calculate the right bucket from each hash code. There is nothing "enhanced" about it, it simply masks away the unused bits. — Paŭlo Ebermann, Apr 08 '11 at 14:12
@Paulo: From MindProd(http://mindprod.com/jgloss/hashtable.html) "Now it is more important than ever to have a high quality hashCode function that has good distribution, especially in the low order bits. It must not favour one bit pattern over another, e.g. not tend to generate hashcodes all ending in binary 0000. In JDK 1.4.1+ there in a rehash function used inside HashMap to improve the quality of your provided hashCode by redistributing the bits. rehash has to be quick, or they might as well have used tables whose lengths are multiples of primes and used the modulus operator." — Dead Programmer, Apr 08 '11 at 14:51
http://stackoverflow.com/questions/4980757/how-do-hashtables-deal-with-collisions — Dead Programmer, Apr 08 '11 at 15:07
@Suresh: Ah, sorry, I somehow have looked at `indexFor` instead of `hash()` in the code you linked at. You are right here. (It still does not really relate to the question about how to manage in the same bucket - these still will occur if the hashCodes of different objects are equal, and still might randomly occur if not.) — Paŭlo Ebermann, Apr 08 '11 at 15:31

score 2 · Answer 1 · answered Apr 08 '11 at 13:00

Well, just a regular HashMap links entries that end up in the same bucket (each bucket is really an element in an array of linked lists). A LinkedHashMap also maintains links between entries to preserve the insertion order, but that's not what's happening in your diagram.

score 1 · Answer 2 · answered Apr 08 '11 at 13:01

1

HashMap does this. What LinkedHashMap does is linking the keys in insertion order.

answered Apr 08 '11 at 13:01

Reddy

8,737
11
55
73

score 1 · Answer 3 · answered Apr 08 '11 at 13:01

I think the standard HashMap already works this way: it has a number of bins, and elements with colliding hash codes end up in the same bin. You can lookup the source code of HashMap yourself: in your JDK installation directory there is a file src.zip that contains the source code.

LinkedHashMap is just a HashMap combined with a List to keep track of the insertion order of elements in the map. The word "linked" in its name doesn't have anything in particular to do with how elements in one bin are stored.

score 0 · Answer 4 · answered Apr 08 '11 at 13:00

You may use HashMap

Map<String,ArrayList<Object>> map = new HashMap<String,ArrayList<Object>>();

Instead of object specify the type you need.

The HashMap grants fast random access. Also there are :

TreeMap - data sorted by key. LinkedHashMap - data stored in order it is entered to the container.

score 0 · Answer 5 · answered Apr 08 '11 at 13:02

LinkedHashMap is for creating a iteratable map that with predictable order of the keys. Internally, a HashHap is free to use whatever means it deems fit to handle key collision which may or may not be a linked list. I don't think there is any standard guarantee that the underlaying mechanism for collision buckets to use a linked list in Java but in practice they may.

Which of Java's hash structures supports 'linear chaining'?

5 Answers5