public V put(K key, V value) { //在添加元素的时候,会先判断是不是为空,如果为空,那么会调用inflateTable方法。这个方法是把HashMap中的数组大小变成capacity*loadFactor,默认是12 if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value); //下面两行代码就是根据key获得它在哪里桶里,获得桶的index。 int hash = hash(key); int i = indexFor(hash, table.length); //循环遍历这个桶中的链表,如果链表中有节点的key跟传进来的key一致,则表示链表中已有数据,这时候将原数据改成新的value。 //如果没有这个值,则会执行下面的addEntry方法 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; } } modCount++; addEntry(hash, key, value, i); return null; } /** * Inflates the table. */ private void inflateTable(int toSize) { // Find a power of 2 >= toSize int capacity = roundUpToPowerOf2(toSize); threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; initHashSeedAsNeeded(capacity); } /** * Adds a new entry with the specified key, value and hash code to * the specified bucket. It is the responsibility of this * method to resize the table if appropriate. * * Subclass overrides this to alter the behavior of put method. */ void addEntry(int hash, K key, V value, int bucketIndex) { //size 表示map中key value键值对的数量。 //threshold是 Hashmap的阈值,如果size大于等于threshold并且 这个链表不为空,则会进行扩容、 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 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, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); } /** * Transfers all entries from current table to newTable. 这个方法中如果被多线程访问,那么可能会造成一个环形链表,当调用get方法时,会由于唤醒链表而导致死循环。 HashMap中的链表在插入节点的时候是用的头插法。因为头插法会导致链表中数据的顺序跟插入的顺序是反过来的。在多线程扩容中,在线程一扩容迁移元素时,会将元素顺序改变,导致两个线程中出现元素的相互指向而形成循环链表,1.8采用了尾插法,从根源上杜绝了这种情况的发生。 当然这个类本身就是线程不安全的,如果想在多线程中用,那么就应该用ConcurrentHashmap. */ void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } }
下面是头插法和尾插法。 我在网上看了很多帖子,发现他们的头插法和尾插法都是一样的,这不扯淡呢吗。。终于找到一个正确的图。让我明白了单向链表哪边是头哪边是尾。
可以看到图左边是链表头,右边是尾, 头插法可以看到,是往左边插入,也就是在头部插入元素,这就导致了元素的顺序是跟插入的先后反过来,而尾插法正好相反。
头插法:
尾插法:
参考链接: