散列表
散列表，又叫哈希表（ Hash Table ），是能够通过给定的关键字直接访问到具体对应的值的一个数据结构。也就是说，把关键字映射到一个表中的位置来直接访问记录，以加快访问速度。散列表是一种空间换时间的存储结构，是在算法中提升效率的一种比较常用的方式。
通常，我们把这个关键字称为 Key，把对应的记录称为 Value。散列的过程需要用到散列函数或者哈希函数。
在散列的过程中有个特殊情况，就是通过不同的 Key，可能访问到同一个地址，这种现象叫作碰撞（Collision）。
散列表为每个对象计算一个整数，称为散列码 （ hashcode )。散列码是由对象的实例域产生的一个整数。具有不同数据域的对象大概率将产生不同的散列码。
Java 中调用对象的 hashCode 方法将会返回该对象的散列码。如果是自定义的类，那么需要实现 hashCode 方法，还需要与 equals 方法相一致，a.equals(b) 返回 true，那么 a 的散列码也要和 b 的相等。
常用的哈希函数
直接寻址法
取关键字或关键字的某个线性函数值为散列地址。
数字分析法
通过对数据的分析，发现数据中冲突较少的部分，并构造散列地址。例如同学们的学号，通常同一届学生的学号，其中前面的部分差别不太大，所以用后面的部分来构造散列地址。
平方取中法
当无法确定关键字里哪几位的分布相对比较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为散列地址。这是因为：计算平方之后的中间几位和关键字中的每一位都相关，所以不同的关键字会以较高的概率产生不同的散列地址。
取随机数法
使用一个随机函数，取关键字的随机值作为散列地址，这种方式通常用于关键字长度不同的场合。
除留取余法
取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为散列地址。这种方式也可以在用过其他方法后再使用。该函数对 m 的选择很重要，一般取素数或者直接用 n。
哈希冲突的常用解决办法
有时不同的 Key 通过哈希函数可能会得到相同的地址，这在我们操作时可能会对数据造成覆盖、丢失。之所以产生冲突是由于哈希函数有时对不同的 Key 计算之后获得了相同的地址。
开放地址法（也叫开放寻址法）
实际上就是当需要存储值时，对Key哈希之后，发现这个地址已经有值了，这时该怎么办？不能放在这个地址，不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希，比如往后移动一个地址，如果没人占用，就用这个地址。如果超过最大长度，则可以对总长度取余。这里移动的地址是产生冲突时的增列序量。
再哈希法
在产生冲突之后，使用关键字的其他部分继续计算地址，如果还是有冲突，则继续使用其他部分再计算地址。这种方式的缺点是时间增加了。
链地址法
链地址法其实就是对 Key通过哈希之后落在同一个地址上的值，做一个链表。在 Java 中的 HashMap、Hashtable 都是用了这种方式。
在 Java 中，散列表用链表数组实现。每个列表被称为桶。要想査找表中对象的位置，就要先计算它的散列码，然后与桶的总数取余，所得到的结果就是保存这个元素的桶的索引。
建立一个公共溢出区
这种方式是建立一个公共溢出区，当地址存在冲突时，把新的地址放在公共溢出区里。
散列表的存储结构
一个好的散列表设计，除了需要选择一个性能较好的哈希函数，否则冲突是无法避免的，所以通常还需要有一个好的冲突处理方式。这里我们选择除留取余法作为哈希函数，选择链地址法作为冲突处理方式。
散列表的特点
散列表有两种用法：一种是 Key 的值与 Value 的值一样，一般我们称这种情况的结构为 Set（集合）；而如果 Key 和 Value 所对应的内容不一样时，那么我们称这种情况为 Map，也就是人们俗称的键值对集合。
根据散列表的存储结构，我们可以得出散列表的以下特点。
访问速度很快
由于散列表有散列函数，可以将指定的 Key 都映射到一个地址上，所以在访问一个 Key（键）对应的 Value（值）时，根本不需要一个一个地进行查找，可以直接跳到那个地址。所以我们在对散列表进行添加、删除、修改、查找等任何操作时，速度都很快。
需要额外的空间
首先，散列表实际上是存不满的，如果一个散列表刚好能够存满，那么肯定是个巧合。而且当散列表中元素的使用率越来越高时，性能会下降，所以一般会选择扩容来解决这个问题。另外，如果有冲突的话，则也是需要额外的空间去存储的，比如链地址法，不但需要额外的空间，甚至需要使用其他数据结构。
这个特点有个很常用的词可以表达，叫作”空间换时间”，在大多数时候，对于算法的实现，为了能够有更好的性能，往往会考虑牺牲些空间，让算法能够更快些。
无序
散列表还有一个非常明显的特点，那就是无序。为了能够更快地访问元素，散列表是根据散列函数直接找到存储地址的，这样我们的访问速度就能够更快，但是对于有序访问却没有办法应对。
可能会产生碰撞
没有完美的散列函数，无论如何总会产生冲突，这时就需要采用冲突解决方案，这也使散列表更加复杂。通常在不同的高级语言的实现中，对于冲突的解决方案不一定一样。
映射 Map
映射用来存放键值对。如果提供了键，就能够查找到值。Java 类库为映射提供了两个通用的实现：HashMap 和 TreeMap。这两个类都实现了 Map 接口。
散列映射 HashMap 对键进行散列，树映射 TreeMap 用键的整体顺序对元素进行排序，并将其组织成搜索
树。如果不需要按照排列顺序访问键，推荐使用散列映射，它有更高的效率。
散列映射 HashMap
最常用的 Map，根据键的 hashCode 值来存储数据。采用链地址法，JDK1.8 后使用数组+链表+红黑树的方式存储数据，根据键可以快速获得它的值。HashMap 中可以允许一条数据的 key 为空。它具有很快的访问速度，遍历时，取得数据的顺序完全是随机的，HashMap 不支持线程同步，即任意时刻可以有多个线程同时写 HashMap，这样对导致数据不一致，如果需要同步，可以使用 Collections.synchronziedMap 的方法使得 HashMap 具有同步的能力或者使用 concurrentHashMap。
散列表 Hashtable
Hashtable 的操作几乎和 HashMap 一致，主要的区别在于 HashTable 为了实现多线程安全，在几乎所有的方法上都加了synchronized 锁，而加锁的结果就是 Hashtable 操作的效率十分低下。
链接散列映射 LinkedHashMap
是 HahsMap 的一个子类，但它保持了记录的插入顺序，遍历时先得到的肯定是先插入的，也可以在构造时带参数，按照应用次数排序，在遍历时会比 HahsMap 慢，不过有个例外，当 HashMap 的容量很大，实际数据少时，遍历起来会比 LinkedHashMap 慢，因为 HashMap 的遍历速度和它容量有关，LinkedHashMap 遍历速度只与数据多少有关。
树映射 TreeMap
实现了 SortMap 接口，能够把保存的记录按照键排序（默认升序），也可以指定排序比较器，遍历时得到的数据是排过序的，底层用红黑树实现。
弱引用散列映射 WeakHashMap
WeakHashMap 使用弱引用（ WeakReference ）保存键。WeakReference 对象将引用保存到另外一个对象中， 在这里， 就是散列键。对于这种类型的对象，垃圾回收器用一种特有的方式进行处理。
private void expungeStaleEntries() { for (Object x; (x = queue.poll()) != null; ) { synchronized (queue) { @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>) x; int i = indexFor(e.hash, table.length); Entry<K,V> prev = table[i]; Entry<K,V> p = prev; while (p != null) { Entry<K,V> next = p.next; if (p == e) { if (prev == e) table[i] = next; else prev.next = next; // Must not null out e.next; // stale entries may be in use by a HashIterator e.value = null; // Help GC size--; break; } prev = p; p = next; } } } }
通常，如果垃圾回收器发现某个特定的对象已经没有他人引用了，就将其回收。然而，如果某个对象只能由 WeakReference 引用， 垃圾回收器仍然回收它，但要将引用这个对象的弱引用放入队列中。 WeakHashMap 将周期性地检查队列，以便找出新添加的弱引用。一个弱引用进人队列意味着这个键不再被他人使用，并且已经被收集起来。于是，WeakHashMap 将删除对应的条目。
WeakHashmap 业务场景就是缓存，可以有效的节省内存。
标识散列映射 IdentityHashMap
IdentityHashMap 这个映射中，键的散列值不是用 hashCode 函数计算的，而是直接使用的对象的内存地址，在对两个对象进行比较的时候使用的是 ==，而不是 equals。
所以IdentityHashMap 有以下特点：
Key 可以相同（内存地址不同）
对于要保存的key，k1和k2，当且仅当k1== k2的时候，IdentityHashMap才会相等，而对于HashMap来说，相等的条件则是：对比两个key的hashCode和equals。
key 可以为 null
IdentityHashMap 不是 Map 的通用实现，它有意违反了 Map 的常规协定。并且 IdentityHashMap 允许 key 和 value 都为 null。
无序、线程不安全
IdentityHashMap 也是无序的，并且该类不是线程安全的，如果要使之线程安全，可以通过下面的方式。
枚举类型映射 EnumMap
如果作为 key 的对象是 enum 类型，那么，还可以使用 Java 集合库提供的一种 EnumMap，它在内部以一个非常紧凑的数组存储 value，并且根据 enum 类型的 key 直接定位到内部数组的索引，并不需要计算 hashCode()，不但效率最高，而且没有额外的空间浪费。
笔记大部分摘录自《Java核心技术卷I》，含有少数本人修改补充痕迹。
