关于上面这是三种数据类型，想必大家对HashMap最为熟悉不过了，但真正对它底层实现原理理解多少呢？是否对源码“走马观花”似的浏览过吗？今天我来讲讲我对这部分的见解，也希望在以后的开发工作中对大家有所帮助。

  这三类容器也就是Map最常见的实现，是以键值对的形式去存储和操作数据的容器类型，：

HashTable：这是java类库中早期实现的哈希表的实现，它本身是同步的，不支持null键和值，由于同步导致的性能开销，所以也不推荐使用。

HashMap：行为上与hashTable类似，主要是它本身是不同步、支持null键值。其get和put操作可以达到常数时间的性能。

TreeMap：基于红黑树的一种提供顺序访问的Map，和HashMap不同，它的get、put、remove操作都是O（logn）的时间复杂度，具体由指定的Comparator来决定，或者根据键的自然顺序来判断。

上面仅仅我们从片面获取的到，并没有更深入的去理解，我下面从以下几点具体分析下：

1，MAP整体结构：

第一 ：   Map整体结构:Hashtable比较特别，作为类似Vector、Stack的早期集合相关类型，它是扩展了Dictionary类的；HashMap等都是扩展了AbstractMap，大部分MAP的场景，都是提供了插入、删除、访问等基本操作，对顺序并没有要求，hashMap是最好的选择，它的性能非常依赖哈希码的有效性，请务必掌握hashCode和equals的基本约定：比如（equals相等，hashcode一定相等；重写hashCode也要重写equals；）；                                         额外说点有序Map，LinkedHashMap和TreeMap都可以保证顺序，前者是双向链表的实现，后者是通过键的顺序去决定存储顺序的。

2，HashMap源码分析：

a，HashMap 内部实现基本点分析：它是可以看做是数组和链表的结合组成的复合结构，数组被分为一个个桶（bucket），通过哈希值决定了在这个数组的寻址；哈希值相同的键值对，则以链表形式存储；如果链表超过阈值，则会被改成树状结构，如下图：

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

public HashMap(int initialCapacity, float loadFactor){

    // ...

    this.loadFactor = loadFactor;

    this.threshold = tableSizeFor(initialCapacity);

}

所以，hashMap也是按照懒加载原则，在首次使用时被初始化。再看看如下putval方法，如果表格是null，resize方法会负责初始化它，或者在容量不够的情况下扩容。该方法不考虑极端情况（容量理论最大极限由MAXIMUM_CAPACITY指定，数值为2的30次方），门限值为负载因子乘以容量。

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()).legth;

    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);

        //  ...

    }

}

3，容量、负载因子和树化：

我们为什么要在乎容量和负载因子呢？这是因为容量和负载因子决定了可用的桶的数量，空桶太多会浪费空间，如果使用太满则会导致性能底下。极端情况下剩一个桶，则就退化成链表了。我们在实践中如何选择呢？如果知道知道键值对数量，可以预先设置容量大小。对于负载因子，我认为：如果没有特殊需求，不要轻易修改，因为JDK默认下的负载因子是最符合通用场景下的，如果需要调整，不要超过0.75，因为会显著增加冲突，降低hashMap的性能，如果使用太小，则会预设容量值会进行调整，否则可能会导致更加频繁的扩容，增加无畏的开销，本身访问性能也会受到影响。                                                                                                                                  对于为什么hashMap要进行树化改造？如果一个对象发生哈希冲突，被放置在同一个桶中，形成链表，要知道链表的查询是线性的，会严重影响效率。而在现实中构造哈希冲突的数据被不难，恶意代码就可以利用这些数据大量与服务器端进行交互，导致服务器CPU大量使用，这就构成了哈希碰撞拒绝服务攻击，国内一线互联网就发生过该类事件。

OK,大概写完了，第一次写博客，一部分是从其他资料挪用过来并加上自己的理解总结的，希望给大家一些帮助。