hashMap

 

关于java.util.hashmap有几个点值得写下来

Hashmap底层由数组构成，其中每一个数组的元素是由HashMap.Entry表示的，每一个entry相当于hashmap中的一个槽slot,hash冲突是由entry里面的next字段解决的，也就通过链表来解决的，如图所示

 

 

成员变量size   就是HashMap里面有多少个槽是被占了的，其实就是每次增加一个entry此值就加1（如果不hash冲突的情况下），如果hash冲突了，当然值就不会加1

 

 

capacity  就是当前hashmap的最大容量，也就是数组的size，其中可能有空闲的slot，

上图hashmap的capacity为6，size为4，也就是有4个slot被占了

 

 

 

load factor  加载因子，主要就是为了控制一个阈值，默认3/4，也就是说size超过了capacity的3/4就需要重新hash了，官方推荐使用默认3/4，在这个值下，时间和空间的消耗可以达到一个平衡

 

threshold  阈值，初始化hashmap会用capacity乘以load factor得到，后续的rehash会重置这个值，通过新容量

newcapacity乘以load factor得到

 

hash collision  hash冲突是值如果想要放入hashmap中的key计算出来的slot位置（其实就是table.index)已经被占了，而且value值也不equals被占的slot中的value值，这个时候就算是hash冲突了

 public V put(K key, V value) {

        if (key == null)

            return putForNullKey(value);

        int hash = hash(key.hashCode());

        int i = indexFor(hash, table.length);

        for (Entry<K,V> e = table[i]; e != null; e = e.next) {

            Object k;

            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

                V oldValue = e.value;

                e.value = value;

                e.recordAccess(this);

                return oldValue;

            }

        }

                以上for循环就是为了解决slot已经被占用时，新要加入的key如果和链表中的key的hash值和key都一样          的话，就用心的value值覆盖掉老的value值，如果不是这种情况，则走下面addEntry将新的entry放入链表的第一个，如果之前没有的话就是唯一一个

 

        modCount++;

        addEntry(hash, key, value, i);

        return null;

    }

 

 

 

 

rehash  重哈希，当hashmap需要增加entry时，如果发现size加1后比阈值threshold还要大(类似需要一个报警），就需要rehash，rehash的时候会用之前capacity的两倍大小建立一个新的hashmap，就算是完成了rehash，这个更大的hashmap又开始工作。。。有一天这个新的hashmap又会变的很满，然后再rehash，可以看到，rehash还是有不少开销的，如果事先知道hashmap会有多大，可以在构造hashmap的时候设定一个capacity以避免频繁rehash，还有有点要说的就是如果并发往hashmap里面塞东西，又不巧又都在同一个slot上发生了hash collision，在那个冲突的slot上可能会发生双向循环链表从而造成死循环，可以使用ConcurrentHashMap解决并发问题

 

 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);

    }

 

 

void resize(int newCapacity) {

        Entry[] oldTable = table;

        int oldCapacity = oldTable.length;

        if (oldCapacity == MAXIMUM_CAPACITY) {

            threshold = Integer.MAX_VALUE;

            return;

        }

 

        Entry[] newTable = new Entry[newCapacity];

        transfer(newTable);

        table = newTable;

        threshold = (int)(newCapacity * loadFactor);

    }

 

更多细节请参考源码：http://www.docjar.com/html/api/java/util/HashMap.java.html