HashMap简史
“Hash Code”这个概念第一次出现是在1953年1月的《Computing literature》中，H. P. Luhn (1896-1964) 在一篇 IBM 的内部备忘录中提出了这个术语。当时 Luhn 是要解决这个问题：“给出组成一本教科书的一系列单词，要得出 100% 完整的（单词，出现页码集）对应关系，最好的算法和数据结构是什么？”
 H.P. Luhn (1896-1964)
|
Luhn 写道， “hashcode” 是基本的运算符。
Luhn 写道， “Associative Array” 是基本的运算数。
由此， ‘HashMap’ (也称为 HashTable) 就这样产生了。
注: HashMap 是由 1896 年出生的计算机科学家提出来的。HashMap 可是个老 家伙啦!
|
从 HashMap 的诞生讲到它的早期应用场景，我们从1950年代跳到1970年代
|
Niklaus Wirth 在他1976年编写的经典著作《算法 + 数据结构 = 程序》中，谈到对于所有的程序，都可以将“算法”视为基本的运算符，将“数据结构”视为基本的运算“数”。
从那时起，数据结构(HashMap，Heap等)发展缓慢。1987年有一个重大突破， Tarjan 提出了非常著名的 F-Heap；但除此之外，乏善可陈。要知道，HashMap 是1953年第一次提出的，已经过去60余年啦！
与此同时，算法方面 (Karmakar 1984, NegaMax 1989, AKS Primality 2002, Map-Reduce2006, Grover’s Quantum search - 2011) 则进展迅速，为计算的基础建设带来了崭新的、强大的运算符。
然而，现在到了2014，也许又轮到数据结构来取得重大进展了。从 OpenJDK 平台来看， 非堆 HashMap 就是一个正在发展的数据结构。
HashMap 的历史就介绍到这。下面我们来探索今天的 HashMap 吧。具体来说，我们先来看一看这个老家伙在 Java 中现存的 3 种实现。
java.util.HashMap (非线程安全) 对于任何真正的多线程并发用例，它会立即失败，而且是每次都会失败。所有用到它的代码必须使用 Java 内存模型(JMM)的内存屏障(memory barrier)策略(如 synchronized 或 volatile) 来保证顺序执行。
假设线程1写入 HashMap，那么它做出的改动只会保存在 CPU 1的1级缓存中。然后线程2，在几秒钟后开始在 CPU 2上运行；它读取 HashMap，是从 CPU 2的1级缓存中读出来的——它看不到线程1做出的改动，因为在读和写的线程中都没有读、写间的内存屏障，虽然 Java 内存模型要求线程共享 HashMap 的情形下必须要有。即使线程1的写操作加了 synchronize 也会失败，这样虽然能把它做出的改动写入到主内存中，但线程2仍然看不到这些改动，因为线程2只会从 CPU 2的1级缓存中读取。所以在写操作上加 synchronized 只能避免写操作的冲突。要对于所有的线程都添加必要的内存屏障，你必须也要 synchronize 读操作。
|
thrSafeHM = Collections.synchronizedMap(hm) ; （粗粒度锁定）
使用“同步”时实现高性能要求低竞争率。这是很常见的，而且在很多情况下这并不像听起来那么坏。然而，一旦你引入任何竞争（多个线程试图同时操作同一集合），性能就会受到影响。在最坏的情况下，如具有很高的锁争用，你可能会得到多个线程比单个线程（操作没有锁定或任何种类的争夺）的性能表现更差的结论。
Collections.synchronizedMap() 返回一个 MT-Safe HashMap.
这是一个通过粗粒度的锁来实现所有关键部分的mutate()和access()操作，这样可以让多个线程操作整个Map。这个结果在Zero MT-concurrency中，意味着一个时刻仅有一个线程可以访问。另一个后果就是作为高锁争用（High Lock Contention）的粗粒度锁，锁住的途径是一种非常不受欢迎的已知条件。关于高锁争用（High Lock Contention）（请看在左边的图片，N个线程争用一个锁，但是迫于阻塞只好等待着，锁已经给了正在运行的线程）。
幸好这是完全同步的，不会真正的同步，隔离（isolation）=序列化（SERIALIZABLE）（总体上这是令人失望的）HashMap陷阱，我们期待的OpenJDK非堆存储（off-heap）JEP已经有一个 值得推荐的期待：硬件事务性内存（Hardware Transactional Memory (HTM)）。关于HTM，粗粒度的同步写操作在Java中将会再一次变得很酷！就让HTM通过代码上的零并发和在硬件的零并发来帮助我们，实现真正的并发并且100%的多线程安全。这很酷，对吧？
幸好这是完全同步的，不会真正的同步，隔离（isolation）=序列化（SERIALIZABLE）（总体上这是令人失望的）HashMap陷阱，我们期待的OpenJDK非堆存储（off-heap）JEP已经有一个 值得推荐的期待：硬件事务性内存（Hardware Transactional Memory (HTM)）。关于HTM，粗粒度的同步写操作在Java中将会再一次变得很酷！就让HTM通过代码上的零并发和在硬件的零并发来帮助我们，实现真正的并发并且100%的多线程安全。这很酷，对吧？
java.util.concurrent.ConcurrentHashMap (线程安全、智能锁，但并非完美)
在jdk1.5的核心API中，终于发布了java程序员梦寐以求的java.util.concurrent.ConcurrentHashMap。虽然ConcurrentHashMap不能广泛替代HashMap（ConcurrentHashMap消耗更多的资源，在低竞争条件下可能不太适合。），但是它解决了其它类型的HashMap解决不了的问题：提供既有真正的多线程安全，又有真正的多线程并发的能力。让我们画一幅画来准确地描述ConcurrentHashMap为什么（原文是how）这么有用的（有效，有作用，不知道怎么翻译好了。原文：helpful）。
1.分离锁
2.每个独立的HashMap子集对应一个锁：N个hash桶（子集）对应N段(Segments)锁。（在图片右边，段(Segments) = 3
3.在设计出将一个高竞争的锁分解成多个不影响数据完整性的锁时，分离锁是非常有用的。
4.更好的并发，在处理"先检查判断状态，再操作"（"check-then-act"）的竞态条件问题时，concurrentHashMap是一个不需要同步的解决方案。
5.问题：你如何同时保护整个集合(collections)? 获取所有的锁(递归地)?
现在你可能要问了：随着ConcurrentHashMap和java.util.concurrent包的发布，java是一个高性能计算社区（High Performance Computing community）能够在上面创建解决方案来解决他们问题的终极编程平台吗？
不幸的是，很现实的一个回答还是“还没呢”。真的，那么还存在着什么问题呢？
ConcurrentHashMap存在着规模问题和保存中间态对象（medium-lived objects）问题。如果你有一小部分使用concurrentHashMap的关键的集合对象，很可能有些会很大。在某些情况下，在这些集合中存在着大量的中间态对象(medium-lived objects)。这些中间态对象(medium-lived objects)贡献了大部分的GC次数（时间,GC pause times），他们的消耗有可能是短暂对象（short-lived objects）的20倍。长时间存活对象(Long-lived objects)往往停留在终身区(tenured space)，短暂对象(short-lived objects)在young区死亡，但是中间态对象(medium-lived objects)会复制到所有的存活空间，并在终身区(trenured space)死亡，中间态对象(medium-lived objects)到处拷贝并在最后被清理产生的消耗十分巨大。最理想的是你能有一个没有GC影响的储存数据的集合。