HashTabe，HashMap,TreeMap底层原理

在这里插入图片描述

Map是广义java集合框架中的另外一部分，HaspMap作为框架中使用频率最高类型之一，我们有必要去深入了解它。

对比 HashMap,HashTable,TreeMap

相同点

HashMap,HashTable,TreeMap都是一些常见的map实现，是以键值对的形式存储和操作数据的容器类型。

不同点

HashTable是早期的Java类库提供的的一个哈希表实现，本身是同步的，不支持null键和空值，由于同步导致的性能开销，使用相当较少。
HashMap是应用更加广泛的哈希表实现，行为上大致和haspTable大致相同，主要区别在于HashMap不是同步的，支持null键和空值。所以性能上更加优秀。
TreeMap是基于红黑树的一种提供顺序访问的Map,和HashMap不同，他的get，put,remove之类的操作都是O（log（n))的时间复杂度，具体顺序可以由指定的Comparator来决定，或者根据键的自然顺序来判断。

HashMap常见问题

haspMap明确声明不是线程安全的的数据结构，所以haspMap在并发环境可能出现无限循环占用cpu，size不准确的诡异问题。

知识扩展

map结构

hashTable和hashMap在类结构上由明显不同

hashMap等其他map实现都hi扩展abstractMap，里面包含了通用的抽象方法，HashMap的性能表现非常依赖于哈希码的有效性。

equals相等，hashcode一定要相等。
重写了hashCode也要重写equals。
hashCode需要保持一致性，状态改变的哈希值仍然要一致。
equals的对称，反射，传递。
LinkedHashMap 和 TreeMap 都可以保证某种顺序，但二者还是很不同的
linkedHashMap通常提供的是遍历顺序符合插入顺序，他的实现是通过条目维护一个双向链表。
对于TreeMap他的整体顺序是由键的顺序关系决定的，通过compartoar来决定。
HashMap源码分析
HashMap 内部实现基本点分析。
容量（capacity）和负载系数（load factor）。
树化
HashMap的内部结构，可以看作是数组和链表组成的复合结构，数组被分成一个个桶数组，通过哈希值在这个桶数组寻址，哈希值相同的键值对，则以链表形式存储。

从非拷贝构造函数的实现来看，这个表格（数组）似乎并没有在最初就初始化好，仅仅设置了一些初始值而已。

public HashMap(int initialCapacity, float loadFactor){  
    // ... 
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

然后看put方法实现

1
2
3

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

put里面调用了putVal方法

final V putVal(int hash, K key, V value, boolean onlyIfAbent,
               boolean evit) {
    Node<K,V>[] tab; Node<K,V> p; int , i;
    if ((tab = table) == null || (n = tab.length) = 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == ull)
        tab[i] = newNode(hash, key, value, nll);
    else {
        // ...
        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for first 
           treeifyBin(tab, hash);
        //  ... 
     }
}

从源码种可以看出
如果表格是null，resize会初始化它
resize方法兼顾两个职责，创建初始存储表格，或者在容量不满足需求的时候进行扩容
在放置新的键值对的时候，如果发生以下情况，就会发生扩容

1 2	`if (++size > threshold) resize();`

具体键值在哈希表种的位置取决于下面的运算

1	`i = (n - 1) & hash`

最后hashMap为什么要树化，本质上是安全问题。因为在元素放置过程中，如果一个对象的哈希冲突，都被放置在一个桶中，会形成一个链表，链表查询是线性的会严重影响存取的性能。