第一，简介
Map 是广义java集合框架中的另外一部分，Hashtable，HashMap，TreeMap 都是常见的一些 Map 实现，是以键值对的形式存储和操作数据的容器类型。
Hashtable 是同步线程安全的，不支持null键和值。
HashMap 是不同步的线程不安全的，支持null键和值。
TreeMap 则是基于红黑树的一种提供顺序访问的 Map，和 HashMap 不同，它的 get，put，remove 之类操作都是O（log(n)）的时间复杂度，具体顺序可以由指定的 Comparator 来决定，或者根据键的自然顺序来判断。
Map 虽然通常被包括在 Java 集合框架里面，但是其本身并不是狭义上的集合类型(Collection)，具体看下图：
Hashtable 比较特别，作为类似 Vector，Stack 的早期集合相关类型，它扩展了 Dictonary类，类结构上和 HashMap 之类明显不同。
HashMap 等其他 Map 实现则是都扩展了 AbstractMap，里面包含了通用的方法抽象。不同 Map 的用途，从类结构就能体现出来，设计目的已经体现在不同接口上。
第二，HashMap原理
HashMap 的底层是 Hash 表数据结构，为什么要底层要使用哈希表？因为快。在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为 O(1)。为什么哈希表会这么快？因为哈希表的主干就是数组。我们知道，数据结构的物理存储结构只有两种：顺序存储结构和链式存储结构。顺序存储结构像数组，对于指定下标的查找，时间复杂度为 O(1)；链式存储结构像链表，查找操作需要遍历链表逐一进行比对，复杂度为 O(n)。
HashMap 内部结构，它可以看作是数组和链表结合组成的复合结构，数组被分为一个个桶（bucket），通过哈希值决定了键值对在这个数组的寻址；哈希值相同的键值对，则以链表形式存储。具体步骤是：当我们将键值对传递给put()方法时，它调用键对象的 HashCode() 方法来计算 HashCode，然后找到 Bucket 位置来储存值对象。如果前后两个键对象的 HashCode 相同，它们的bucket位置就会相同，这时就发生了哈希碰撞也叫哈希冲突，为了解决哈希碰撞，HashMap 使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在同一个Bucket 位置链表的下一个节点中。当获取对象时调用 get() 方法，HashMap 会使用键对象的 HashCode 找到bucket位置，如果有两个值对象储存在同一个 Bucket，将会遍历链表通过键对象的 equals()方法找到正确的键值对，然后返回值对象。
HashMap 是一个容器，既然是容器就会设计到扩容，HashMap 是怎么扩容的呢？HashMap 因为为了避免浪费内存空间和减少哈希碰撞的几率，HashMap 引入了加载因子这个变量，HashMap 加载因子默认值是0.75意味着当 HashMap 的使用容量占到总容量的 0.75 时就会扩容一倍。
HashMap 我们在应用中经常使用，但是要注意的一点是 HashMap 是非线程安全的，在多线程使用 HashMap 会出现什么异常呢？因为在多线程中的 HashMap，当需要重新调整HashMap 大小时，可能会存在条件竞争，在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap 并不会将元素放在链表的尾部，而是放在头部。假如有两个线程 P1、P2以及链表 a->b。P1 先运行链表翻转为 b->a 这时线程阻塞，P2 运行链表再翻转为 a->b，然后 P1 再运行，就这样条件竞争发生了，成了死循环。所以在多线程中建议使用基于分离锁实现的 ConcurrentHashMap，它比 HashTable 大大提高了效率，因为 HashTable 的实现基本就是将 put，get，size 等方法加上 synchronized ，这就导致了所有并发操作都要竞争同一把锁，一个线程在进行同步操作时，其他线程只能等待，大大降低了并发操作的效率。
看下图：如果链表大小超过阈值 (TREEIFY_THRESHOLD，8)，图中的链表就会被改造成为树形结构（哈希碰撞频繁，导致链表过长，查询时间陡升，黑客则会利用这个『漏洞』来攻击服务器，让服务器CPU被大量占用，从而引起了安全问题。 而树化(使用红黑树）能将时间复杂度降到 O(logn)，从而避免查询时间过长）。
网友评论