Sean

hashmap

07 October 2015

the internal data structure of hashmap is array of Map.Entry, in jdk1.7, Entry is a key-value pair, it is also a linkedlist, which contains the reference of the next element. wait, aren’t we takling about hashmap? why there is linkedlist?

 static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

	...
 }

right, when we put an entry into hashmap, it first create the hash by key, if the key is String, then use sun.misc.Hashing.stringHash32 to create the hash, then find the bucket by the hash, it will return the position of the bucket.

  public V put(K key, V value) {
  ...
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  ...
  }

  final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
   }

   static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

after find the position of the bucket, it’s time to add the entry to the bucket.

 void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

it first check if the size of current table (array) has exceed the threshold and the bucket is not null, that means the current hashmap is full, we need to expand it. after the map expanded, we need to recalculate the bucketindex by indexFor

after the new bucketindex founded, create a new entry in that bucket, the process of create an entry is

  1. get the head of linkedlist in the bucket,
  2. then replace that with the new entry,
  3. then keep the reference of the head to the next property of the entry

find entry

final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

when get entry

  1. find the bucket index by key
  2. compare the key of the linkedList item in the bucket until the entry was found
blog comments powered by Disqus