HashMap简析之-HashCode冲突的解决

总述:通过一定的算法,将key的hashcode转换成数组的index;将key,value,hash等信息保存在数组对应的index位置上.

 

问题:

1.某些key的hashcode相同

2.hashcode不同,但一定算法后映射到数组的index相同

这个就是常说的hashcode冲突问题.

 

1.HashMap涉及的数据结构

   Entry[] ;

   //Entry数组:存储HashMap元素的地方.

   //Entry

   //1.封装了key;value;

   //2.本身是一个单向链表;包含hash值;next;指针;

  

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

        /**
         * Create new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

         ....
}

 

  

 

2.存储的过程:

 

通过hashcode得到index后.存储的不仅仅是该元素的key,value,hash.还有指向下一个Entry的引用.如果出现了hashcode冲突问题.则新建一个Entry;将该Entry的nex指针指向已存在的Entry.

  

public V put(K key, V value) {
        K k = maskNull(key);
        int hash = hash(k);                    //算hash
        int i = indexFor(hash, table.length);  //取对应的index
        //该index对应的Entry可能不是一个Entry,而是一个Entry链.
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            if (e.hash == hash && eq(k, e.key)) { //已存在,则更新值.
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, k, value, i); //该位置还空;或者位置不空,但已有Entry(hashcode冲突)
        return null;
    }

 

   void addEntry(int hash, K key, V value, int bucketIndex) {
            //取到当前位置上的Entry,可能是null
            Entry<K,V> e = table[bucketIndex];
            //创建新Entry,next指向已存在的
            table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        
            if (size++ >= threshold)
                     resize(2 * table.length);//扩容.
    }

 

 

 

 

3.取值的过程

 

还是hash-index-Entry的过程.不是直接return该index上Entry;而要检查Entry链上真正对应的那个

    public V get(Object key) {
        Object k = maskNull(key);
        int hash = hash(k); //取hash
        int i = indexFor(hash, table.length);//取index
       
        //取回来的是一个Entry链
         Entry<K,V> e = table[i]; 
        //遍历
         while (true) {
            if (e == null)
                return null;
            if (e.hash == hash && eq(k, e.key)) //真正要get的那个
                return e.value;
            e = e.next; //指针后移到下一个Entry
        }
    }

 

算个复习吧.没看过的看看.笔试面试很常见.

评论

1 楼 步青龙 2012-04-12  

好文章 赞一个