HashMap

HashMap学习

jdk源码的学习最重要是掌握学习方法

集合hashMap的学习

1. 确定存储结构

基于jdk1.7

1.存储对象结构

int DEFAULT_INITIAL_CAPACITY=1<<4 2^4=16

int MAXIMUM_CAPACITY 1<<30 2^30

float DEFAULT_LOAD_FACTOR 0.75f

2.确定结构

经查看类里面调用情况，table成员可以确定为hashmap里面存储对象的结构定义

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

通过类功能、结构去推测。

hashMap存储对象结构为一个数组，数组内数据为Entry<k,v>, 该类为hashmap的内部类。

3.每个put内容都是转成了一个entry实例进行存储：

4.put一条新数据

public V put(K key, V value) {
    //若 table数组为空，则初始化
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    //计算hash、用户确定数据存储在数组那个位置
    int hash = hash(key);
    //计算数据存储在数组那个位置
    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;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    //用来返回大于等于最接近number的2的冪数
    int capacity = roundUpToPowerOf2(toSize);

    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

hashmap 的数据结构为数组+链表结构

新增一个数据时

• key已存在，覆盖原数据
• key不存在
  • 发生冲突，在原位置设置当前新值，新值的下一个节点为旧节点数据
  • 不发生冲突，直接在数组位置设置entry

查询数据时：

 确定在数组的位置，再遍历当前位置上的链表

jdk：工具，提供高性能、便捷、持久维护

hashmap 结构提高数组的查询速度，所以需要限制链表的长度，

数组扩容：

    map中元素数量>阈值，并且本次冲突

     阈值=12

hashmap扩容前最大能存储27个元素， 12+15；

扩容为：原来数组的两倍大小；