JDK1.7 数组+链表
JDK1.8及以上 数组+链表+红黑树
/** * The default initial capacity - MUST be a power of two. * 默认初始容量,必须是2的指数幂 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */ static final int MAXIMUM_CAPACITY = 1 << 30;
当然我们可以随意指定一个大小,比如9,但是在put元素时,hashmap会将9进行处理,强制转换成2的指数幂并且大于9、最接近9的数值
public V put(K key, V value) { // 判断map是否为空,如果是空的则处理容量大小是否满足2的指数幂要求 if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value); int hash = hash(key);
private static int roundUpToPowerOf2(int number) { // assert number >= 0 : "number must be non-negative"; return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1; }
/** * The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next;// hash值相同的下一个元素指针 int hash; /** * Creates new entry. */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; }
不同的数据计算出来的hash值是一样的,称为hash碰撞
遍历整个table数组,判断数组中的元素hash值与当前hash值相同,并且key相同,则将这个元素的value更新为当前需要存储的value,并返回旧value值
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; } }
如果不需要则创建新的元素,并将新的元素指向老的元素
1)、从table数组中取出对应下标位置链表对象
2)、创建新的链表对象将其赋给table数组对应下标位置,并将新创建的链表对象指针指向原链表对象
void createEntry(int hash, K key, V value, int bucketIndex) { // 1、从**table数组**中取出对应下标位置链表对象 Entry<K,V> e = table[bucketIndex]; // 2、创建新的链表对象将其赋给table数组对应下标位置,并将新创建的链表对象指针指向原链表对象 table[bucketIndex] = new Entry<>(hash, key, value, e); size++; }
1)扩容为数组原来的2倍容量
if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); // 扩容为2倍 hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); }
2)将当前数组所有数据转移到新创建的数组中
大致流程:遍历数组每个链表项,依次将链表数据插入新创建的数组的某个位置中,采用的是头插法(newTable[i] = e),即遍历链表得到的数据都是往新数组链表根节点存放,最后转移到新数组中链表中数据顺序与原数组链表数据顺序是相反的
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; } } }
如上图示例,将左边数组转移到右边数组下标1的位置,详细转移过程如下:
声明2个变量:e、next,分别指向张三、李四
执行e.next = newTable[i],将张三的next指向1
执行newTable[i] = e,将张三移到1的位置
执行e = next,将e指向李四,第一遍循环结束
第二遍循环开始,执行Entry<K,V> next = e.next,此时next为null
执行e.next = newTable[i],将李四的next指向张三
执行newTable[i] = e,将李四插入原来张三所在位置
执行e = next,将e指向null,第二遍循环结束
执行while(null != e) ,此时e == null不满足条件,扩容结束,可看到扩容结束后,张三与李四位置已互换
假设此时有2个线程同时进入该方法执行扩容,2个线程分别创建了新数组进行扩容,并各自声明2个变量指向张三、李四,而线程二在执行Entry<K,V> next = e.next;代码之后因为某种原因卡顿了一下,此时线程一已完成第一遍循环,
线程二开始执行e.next = newTable[i],newTable[i] = e;将张三移到新数组下标1位置
执行e = next,将e指向李四,线程二第一遍循环结束
线程二第二遍循环开始,执行Entry<K,V> next = e.next,将next指向null
执行e.next = newTable[i],这里李四本身就指向张三
执行newTable[i] = e,e = next;这里newTable[i]存的是张三,因此将张三指向李四,e指向null,此时出现了闭环,李四指向张三,张三指向李四
如上过程所示