HashMap

在数据结构中我门学习过很多种查找的方式比如顺序查找，折半查找（二分查找），分块查找以及此topic中提到的散列查找。

散列查找也为哈希查找，哈希查找的时间复杂度为O(1)，插入的时间复杂度也为O(1)，有着比较好的性能，但是始终存在一个难以解决的问题就是哈希冲突。

为了解决这个冲突，衍生出很多的解决办法
1. 拉链法（将有哈希冲突的字符串成一个链表）
2. 开放地址法
  1. 线性探测法
  2. 平方探测法
  3. 为随机序列法
  4. 以上方法的本质思想都相同，就是如果遇到了冲突就查找currentPostion+di 每种方法的di都不同此文章就不多加赘述，如有兴趣可以参考数据接口散列查找部分、
3. 再散列法（准备多个散列函数）

在Java中的HashMap就采用了拉链法来解决hash冲突

HashMap的大致结构

从这个图中我我们就可以大致了解hashmap是如何解决hash冲突的。当有hash冲突的时候（hash函数映射到了一个被占用的数组的位置）就加入到这个链表中。

在这里插入图片描述

HashMap的结构

这里hashmap使用了一个Entry数组来作为他的主干，当没有hash冲突的时候，键值对就存放在Entry数组中

这个entry 实现了Map.Entry这个接口

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

transient int size;

// 初始为16
int threshold;

// 负载因子 用来尽可能的减少hash冲突，如果等到容量满了才扩容那么每一个Entry数组下面挂着的链可能就很长了，我们要在Entry数组满之前就扩容
final float loadFactor;

// HashMap改变的次数，
// HashMap是非线程安全的，如果在迭代的过程中，hashmap的modCount改变了，那么就会抛出一个ConcurrentModificationException异常
transient int modCount;

HashMap初始化

public HashMap(int initialCapacity, float loadFactor) {
	　
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);

    this.loadFactor = loadFactor;
    threshold = initialCapacity;
　　　　　
    init();
}

可以看出在刚初始化其实HashMap是空的仅有两个int占用8字节的内存，并没有给Entry数组，真正的分配空间。

HashMap插入：

public V put(K key, V value) {
		// 如果table还是空的，也就是刚初始化后，第一次插入数据，给table数组分配空间
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
	  // 如果key为null，对这个entry单独处理
		// Note：HashMap是允许键为null，但是只能有一个key为null
    if (key == null)
        return putForNullKey(value);
		// 计算key的hash值
		// 也就是散列值，可以让他分布的更均匀，大部分的key都有不一样的hash值
		// 当hash值相同后就产生了hash冲突
    int hash = hash(key);
		// 获取此hash值对应数组的位置
		// 函数内部实现：hash & (length-1)
		// 我们一般的操作是hash % length 这样可以保证得到的位置在数组内
		// 但是对于HashMap，对这个做了优化，采用位运算，速度更快同时可以达到得到的值在[0,length-1]的范围内    
		int i = indexFor(hash, table.length);
		// 这里其实就是已经定位到了，table数组的位置，查找数组下的链表
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    
        Object k;
				// 如果有两个key相同，则覆盖以前的value，返回原来的value
				// 仅仅是hash值相同还不够，需要key和节点上的key相同才能保证这两个key相同
				// 对于int类型== 就可以验证两个key相同
				// 但是对于key为对象时 == 对比的是两个对象的地址 .equals才可以验证两个对象内部数据相同
        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);//新增一个entry
		// 如果添加的key是新的那么返回null
    return null;
}

真正的初始化table

private void inflateTable(int toSize) {
		// 将capacity也就是在put的时候传入的threshhold，扩大到2次幂
    int capacity = roundUpToPowerOf2(toSize);
    // 此处才是真的threshold的赋值
		// threshold = capacity*loadfactor 最小值为MAXIMUM_CAPACITY + 1，
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

介绍一下addEntry的具体实现

void addEntry(int hash, K key, V value, int bucketIndex) {
	  // 在HashMap的大小在临界值，且发生了hash冲突
		// 则扩容
    if ((size >= threshold) && (null != table[bucketIndex])) {
				// 大小变为原来的两倍
        resize(2 * table.length);
				// 通过key找到合适的数组下标位置
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

从上面的代码我们可以知道当size大于等于阈值且发生了hash冲突，就对table扩容，新建一个两倍原来数组大小的新数组，并将现在的元素全部转移过去，这是一个非常time-consuming的操作因为要全部重新计算hash并得到新的数组下标因为数组的长度已经改变了。

Resize方法

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
		// 新建一个table
    Entry[] newTable = new Entry[newCapacity];
		// 将老得table的值转移到新的table中
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
　　　　　//for循环中的代码，逐个遍历链表，重新计算索引位置，将老数组数据复制到新数组中去（数组不存储实际数据，所以仅仅是拷贝引用而已）
    // 对所有数组中的链表映射到新的数组中的链表中
		for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
						// 对每一个元素都重新计算hash值
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
						// 得到在新数组中的数组位置
            int i = indexFor(e.hash, newCapacity);
						// 这一步操作等于是在新的链表头部插入entry
            e.next = newTable[i];
            newTable[i] = e;
						// e指向他的下一个节点
            e = next;
        }
    }
}

保持数组长度一直是二次幂的原因是可以保证元素在老数组中和新数组中的index变化不会太大，举一个例子比如本来的length是16 二进制为10000，length-1为01111，同理扩容后的数组长度是32，二进制表示为100000,length-1为011111。我们可以上下对比一下仅有一位的差异，所以大多数的key的映射到的数组下表都是相同的。

这是我的理解：其实length-1 肯定是低位全一，直接取hash的低位可以保证在数组大小内。只有二次幂的数-1才有这个性质。

从HashMap中取数据

public V get(Object key) {
	　// 如果key为空直接取table[0]处检索即可
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);
    return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
    // 如果没数据直接返回null
    if (size == 0) {
        return null;
    }
    // 首先通过hash函数找到数组下标位置，然后在搜索链表解决hash冲突
    int hash = (key == null) ? 0 : hash(key);
    //indexFor (hash&length-1) 获取最终数组索引，然后遍历链表，通过equals方法比对找出对应记录
    // 找到了数组下表后就开始顺序遍历链表找到对应的值
		for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
				// 仅仅是hash值相同还不够，需要key和节点上的key相同才能保证这两个key相同
				// 对于int类型== 就可以验证两个key相同
				// 但是对于key为对象时 == 对比的是两个对象的地址 .equals才可以验证两个对象内部数据相同
        if (e.hash == hash && 
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}