hashmap源码分析

很早之前就写了这篇文章，最近整理文档代码，看见了，就放在博客中吧。

 

java编码中我们用的最多的数据结构就是set，map和list。其中最常用的hashmap，让我们看看的源码实现吧。

 

 总的来说HashMap的实现是用一个链表类型的数组，也就是说数组中的元素是链表。链表类型是Entry是个内部类，源代码如下：

 

 

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

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

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final V setValue(V newValue) {
	    V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        public final int hashCode() {
            return (key==null   ? 0 : key.hashCode()) ^
                   (value==null ? 0 : value.hashCode());
        }

        public final String toString() {
            return getKey() + "=" + getValue();
        }

        /**
         * This method is invoked whenever the value in an entry is
         * overwritten by an invocation of put(k,v) for a key k that's already
         * in the HashMap.
         */
        void recordAccess(HashMap<K,V> m) {
        }

        /**
         * This method is invoked whenever the entry is
         * removed from the table.
         */
        void recordRemoval(HashMap<K,V> m) {
        }
    
    }

 

       数组的下标是通过key值的hash值与数组的长度计算出来的。而链表是用用来存放一些具有相同的hashcode， 不是同一个对象或者对象的equals方法不相等的对象，后put过来的这些对象的会放在链表的头部位置。

 

      看看它的put方法，在源码部分加了一些注释：

public V put(K key, V value) {
	K k = maskNull(key);//HashMap可是支持空值的哟
        int hash = hash(k);//做一些数据处理

        int i = indexFor(hash, table.length);//根据key值的hash值与数组的长度计算出来数组的下标

	   //下面这个for循环用来判断put进来的key值此数组位置上的链表中的Entry是否hash和equals方法都相等，如果
	 //相等就替换此位置的值，并返回替换之前的值。
        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);
        return null;
    }


 void addEntry(int hash, K key, V value, int bucketIndex) {
//新元素放置在链表的头部
	Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
           //超过数组的阀值大小就扩大两倍。
            resize(2 * table.length);
    }

static int indexFor(int h, int length) {
        return h & (length-1);
    }
 static int hash(Object x) {
        int h = x.hashCode();

        h += ~(h << 9);
        h ^=  (h >>> 14);
        h +=  (h << 4);
        h ^=  (h >>> 10);
        return h;
    }

 

 

 

hashset的底层其实也是用的是HashMap 。