HashList与HashSet

散列表

也叫哈希表

散列表本质是数组存储，通过 key-value 的形式存储数据，所以当取 value 的时候，实际上取数组某个位置的元素，并且以 key 的 hashCode 作为 value 在数组中的位置。

List vs Set

1、List 是按 add 顺序存储，且元素可以重复，元素有索引，可以根据元素位置进行 get。
2、Set 存储元素无序(hashCode)，元素不可重复(HashMap)，没有 get 方法，只能通过迭代器获取元素。

private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map 
private static final Object PRESENT = new Object(); 
public boolean add(E e) { 
    return map.put(e, PRESENT)==null; 
}

HashMap

1. 相同的键值对将被覆盖。需保证Key已经 重写equals()
2. 存储位置与Key的hashcode()相关，需确保 重写hashcode()

equals
    Object：返回==，判断地址
    String：== && 所有字符相等
    

3. 最多允许一条数据的Key为Null，可允许多条的值为Null
4. 存储数据的顺序不确定，且可能因为扩容而数据改变
5. 数组的存储方式在内存的地址是连续的，大小固定，一旦分配不能被其他引用占用。它的特点是查询快，时间复杂度是O(1)，插入和删除的操作比较慢，时间复杂度是O(n)，链表的存储方式是非连续的，大小不固定，特点与数组相反，插入和删除快，查询速度慢。

原理

image

1. key == Null? Enrty[0] : 步骤2
2. key的 hashCode() 经过两次Hash，特征值是int
3. 对Entry[]的length求余hash & (length-1)，得到Entry的index
4. 如果该位置上已经有元素了，就说明存在hash冲突，这样会在index位置生成链表

JDK的String的Hash算法

public int hashCode() { 
    int h = hash; 
    if (h == 0 && value.length > 0) {
        char val[] = value; 
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        } 
        hash = h; 
    }
    return h; 
} 

选择31是因为它是一个奇素数，如果它做乘法溢出的时候，信息会丢失，而且当和2做乘法的时候相当于移位。
31的一个很好的特性就是做乘法的时候可以被移位和减法代替的时候有更好的性能体现。例如31i相当于是i左移5位减去i，即31i == (i<<5)-i。现代的虚拟内存系统都使用这种自动优化

put方法

1. 判断key是否已经存在，存在则替换，返回旧值
2. 检查容量是否到达阈值threshold
3. 如果元素个数已经达到阈值，则扩容，
    并把原来的元素移动过去。
4.扩容实现：这里会新建一个更大的数组
    并通过transfer方法，移动元素。
5.移动的逻辑：遍历原来table中每个位置的链表，
    并对每个元素进行重新hash，
    在新的newTable找到归宿，并插入。
    
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; 
        }
    } 
}