First, you have to understand a what a hash function is. A hash function is a function that takes a key (for example, an string of arbritrary length) and returns a number as unique as possible. The same key must always return the same hash. A really simple string hashing function in java might look like

public int stringHash(String s) { int h = s.length(); for(char c : s.toCharArray()) { h ^= c; } return h; } 

You can study a good hash function at http://www.azillionmonkeys.com/qed/hash.html

Now, the hash map uses this hash value to place the value into an array. Simplistic java method:

public void put(String key, Object val) { int hash = stringHash(s) % array.length; if(array[hash] == null) { array[hash] = new LinkedList<Entry<String, Object> >(); } for(Entry e : array[hash]) { if(e.key.equals(key)){ e.value = val; return; } } e.add(new Entry<String, Object>(key, val)); } 

(This map enforces unique keys. Not all maps do.)

It is possible for two different keys to hash to the same value, or two different hashes to map to the same array index. There exists many techniques for dealing with this. The simplest is to use a linked list (or binary tree) for each array index. If the hash function is good enough, you will never need a linear search.

Now to look up a key:

public Object get(String key) { int hash = stringHash(key) % array.length; if(array[hash] != null) { for(Entry e : array[hash]) { if(e.key.equals(key)) return e.value; } } return null; } 

First, you have to understand a what a hash function is. A hash function is a function that takes a key (for example, an string of arbritrary length) and returns a number as unique as possible. The same key must always return the same hash. A really simple string hashing function in java might look like

public int stringHash(String s) { int h = s.length(); for(char c : s.toCharArray()) { h ^= c; } return h; } 

You can study a good hash function at http://www.azillionmonkeys.com/qed/hash.html

Now, the hash map uses this hash value to place the value into an array. Simplistic java method:

public void put(String key, Object val) { int hash = stringHash(s) % array.length; if(array[hash] == null) { array[hash] = new LinkedList<Entry<String, Object> >(); } for(Entry e : array[hash]) { if(e.key.equals(key)){ e.value = val; return; } } array[hash].add(new Entry<String, Object>(key, val)); } 

(This map enforces unique keys. Not all maps do.)

It is possible for two different keys to hash to the same value, or two different hashes to map to the same array index. There exists many techniques for dealing with this. The simplest is to use a linked list (or binary tree) for each array index. If the hash function is good enough, you will never need a linear search.

Now to look up a key:

public Object get(String key) { int hash = stringHash(key) % array.length; if(array[hash] != null) { for(Entry e : array[hash]) { if(e.key.equals(key)) return e.value; } } return null; }