一, HashMap
1.HashMap 概述:
HashMap 是基于哈希表的 Map 接口的非同步实现. 此实现提供所有可选的映射操作, 并允许使用 null 值和 null 键. 此类不保证映射的顺序, 特别是它不保证该顺序恒久不变.
2.HashMap 的数据结构:
在 Java 编程语言中, 最基本的结构就是两种, 一个是数组, 另外一个是模拟指针(引用), 所有的数据结构都可以用这两个基本结构来构造, HashMap 也不例外. HashMap 实际上是一个 "链表散列" 的数据结构, 即数组和链表的结合体. 如下图, HashMap 底层就是一个数组结构, 数组中的每一项又是一个链表. 当新建一个 HashMap 的时候, 就会初始化一个数组.
源码:
- /**
- * The table, resized as necessary. Length MUST Always be a power of two.
- */
- transient Entry[] table;
- static class Entry<K,V> implements Map.Entry<K,V> {
- final K key;
- V value;
- Entry<K,V> next;
- final int hash;
- ......
- }
Entry 就是数组中的元素, 每个 Map.Entry 其实就是一个 Key-Value 对, 它持有一个指向下一个元素的引用, 这就构成了链表.
3.HashMap 的存储实现:
- public V put(K key, V value) {
- // HashMap 允许存放 null 键和 null 值.
- // 当 key 为 null 时, 调用 putForNullKey 方法, 将 value 放置在数组第一个位置.
- if (key == null)
- return putForNullKey(value);
- // 根据 key 的 keyCode 重新计算 hash 值.
- int hash = hash(key.hashCode());
- // 搜索指定 hash 值在对应 table 中的索引.
- int i = indexFor(hash, table.length);
- // 如果 i 索引处的 Entry 不为 null, 通过循环不断遍历 e 元素的下一个元素.
- for (Entry<K,V> e = table[i]; e != null; e = e.next) {
- Object k;
- if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
- V oldValue = e.value;
- e.value = value;
- e.recordAccess(this);
- return oldValue;
- }
- }
- // 如果 i 索引处的 Entry 为 null, 表明此处还没有 Entry.
- modCount++;
- // 将 key,value 添加到 i 索引处.
- addEntry(hash, key, value, i);
- return null;
- }
从源码得: 当我们往 HashMap 中 put 元素时, 先根据 key 的 hashCode 重新计算 hash 值, 根据 hash 值得到这个元素在数组的位置(下标), 如果数组该位置已经存放了其他元素了, 那么在这个位置上的元素将以链表的形式存放, 新加入的放在链头, 最先加入的放在链尾. 如果数组该位置上没有元素, 就直接将该元素放到此数组中的该位置上.
addEntry(hash,key,value,i)方法根据计算出的 hash 值, 将 Key-Value 对放在数组 table 的 i 索引处. addEntry 是 HashMap 提供的一个包访问权限的方法, 方法如下:
- void addEntry(int hash, K key, V value, int bucketIndex) {
- // 获取指定 bucketIndex 索引处的 Entry
- Entry<K,V> e = table[bucketIndex];
- // 将新创建的 Entry 放入 bucketIndex 索引处, 并让新的 Entry 指向原来的 Entry
- table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
- // 如果 Map 中的 key-value 对的数量超过了极限
- if (size++>= threshold)
- // 把 table 对象的长度扩充到原来的 2 倍.
- resize(2 * table.length);
- }
当系统决定存储 HashMap 中的 Key-Value 对时, 完全没有考虑 Entry 中的 Value, 仅仅只是根据 key 来计算并决定每个 Entry 的存储位置. 即当系统决定了 key 的存储位置之后, value 随之保存在那里即可.
hash(int h)方法根据 key 的 hashCode 重新计算一次散列. 此算法加入了高位计算, 防止低位不变, 高位变化时, 造成的 hash 冲突.
- static int hash(int h) {
- h ^= (h>>> 20) ^ (h>>> 12);
- return h ^ (h>>> 7) ^ (h>>> 4);
- }
我们得知在 HashMap 中要找到某个元素, 需要根据 key 得到 hash 值来求得对应数组中的位置. 如何计算这个位置就是 hash 算法. 上面说过 HashMap 的数据结构是数组和链表的结合, 所以我们当然希望这个 HashMap 中的元素位置尽量的分布均匀些, 尽量使得每个位置上的元素数量只有一个, 那么当我们用 hash 算法求得这个位置的时候, 马上就可以知道对应位置的元素就是我们要的, 而不用再去遍历链表, 这样就大大的优化了查询的效率.
对于任意给定的对象, 只要它的 HashCode()返回值相同, 那么程序调用 Hash(int h)方法所计算得到的 hash 值总是相同的. 我们首先想到的就是把 Hash 值对数组的长度取模运算, 这么一来, 元素的分布相对来说是比较均匀的. 但是模运算的消耗还是比较大的, HashMap 中: 调用 indexFor(int h,int length)方法来计算该对象应该保存在 table 数组的哪个索引处.
- static int indexFor(int h, int length) {
- return h & (length-1);
- }
HashMap 底层数组的长度总是 2 的 n 次方, 这是 HashMap 在速度上的优化.
当数组长度为 2 的 n 次幂的时候, 不同的 Key 算得的 index 相同的几率较小, 那么数据在数组上分布就比较均匀, 也就是碰撞的几率. 比较小. 相对的, 查询的时候就不用遍历某个位置上的链表, 这样查询的效率也就比较高了.
4.HashMap 的读取实现:
- public V get(Object key) {
- if (key == null)
- return getForNullKey();
- int hash = hash(key.hashCode());
- for (Entry<K,V> e = table[indexFor(hash, table.length)];
- e != null;
- e = e.next) {
- Object k;
- if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
- return e.value;
- }
- return null;
- }
从 HashMap 中 get 元素时, 首先计算 key 的 hashCode, 找到数组中对应位置的某一个元素, 然后通过 key 的 equals 方法在对应位置的链表中找到需要的元素. 即: HashMap 在底层将 key-Value 当成一个整体进行处理, 这个整体就是一个 Entry 对象. HashMap 底层采用了一个 Entry[]数组来保存所有的键值对, 当需要存储一个 Entry 对象时, 会根据 hash 算法来决定其在数组中的存储位置, 在根据 equals 方法决定其在该数组位置上的链表中的存储位置; 当需要取出一个 Entry 时, 也会根据 hash 算法找到其在数组中的存储位置, 在根据 equals 方法从该位置上的链表中取出该 Entry.
5.HashMap 的 resize(rehash):
当 hashMap 中的元素越来越多的时候, hash 冲突的几率也越来越高, 因为数组的长度是固定的. 所以为了提高查询的效率, 就要对 HashMap 的数组进行扩容, 数组扩容这个操作也会出现在 ArrayList 中, 这是一个常用的操作, 而在 HashMap 数组扩容之后, 最消耗性能的点就出现了: 原数组中的数据必须重新计算其在新数组中的位置, 并放进去, 这就是 resize. 当 HashMap 中的元素个数超过数组大小 loadFactor 时, 就会进行数组扩容, loadFactor 的默认值为 0.75, 这是一个折中的取值. 也就是说, 默认情况下, 数组大小为 16, 那么当 HashMap 中元素个数超过 16*0.75=12 的时候, 就把数组的大小扩容为 2*16=32, 即扩大一倍, 然后重新计算每个元素在数组中的位置, 而这是一个非常消耗性能的操作, 所以如果我们已经预知 HashMap 中元素的个数, 那么预设元素的个数能够有效的提高 HashMap 的性能.
6.Fail-Fast 机制:
我们知道 HashMap 不是线程安全的, 因此如果在使用迭代器的过程中有其他线程修改了 Map, 那么将抛出 ConcurrentModificationException, 这就是所谓 fail-fast 策略. 这一策略在源码中的实现是用过 modCount 域 (修改次数) 对 HashMap 内容的修改都将增加这个值, 那么在迭代器初始化过程中会将这个值赋给迭代器的 expectModCount. 在迭代过程中, 判断 modCount 跟 expectModCount 是否相等, 如果不想等就表示已经有其他线程修改了 Map.(modCount 声明为 volatile, 保证了线程之间的可见性).
- final Entry<K,V> nextEntry() {
- if (modCount != expectedModCount)
- throw new ConcurrentModificationException();
7. 关于 HashMap 的问题:
为什么 String,Integer 这样的 wrapper 类适合作为键?
String,Integer 这样的 wrapper 类作为 HashMap 的键是在适合不过了, 而且 String 最为常用, 因为 String 是不可变的, 也是 final 的, 而且已经重写了 equals()和 hashCode()方法了. 其他的 wrapper 类也有这个特点. 不可变性是必要的, 因为为了要计算 HashCode(), 就要防止键值改变, 如果键值在放入时和获取时返回不同的 hashCode 的话, 那么就不能从 HashMap 中找到你想要的对象. 不可变性还有其他的优点如线程安全. 如果你可以仅仅通过将某个 field 声明成 final 就能保证 hashCode 是不变的, 那么请这么做. 因为获取对象的时候要用到 equals()和 hashCode()方法, 那么键对象正确的重写这两个方法是非常重要的. 如果两个不相等的对象返回不同的 hashCode 的话, 那么碰撞的几率就会小些, 这样就能提高 HashMap 的性能.
我们可以使用自定义的对象作为键吗?
这是前一个问题的延伸. 当然你可能使用任何对象作为键, 只要它遵循了 equals()和 hashCode()方法的定义规则, 并且当对象插入到 Map 中之后将不会再改变了. 如果这个自定义对象时不可变的, 那么它已经满足了作为键的条件, 因为当它创建之后就已经不能改变了.
我们可以使用 ConcurrentHashMap 来代替 HashTable 吗?
这是另外一个很热门的面试题, 因为 ConcurrentHashMap 越来越多人用了. 我们知道 HashTable 是 synchronized 的, 但是 ConcurrentHashMap 同步性能更好, 因为它仅仅根据同步级别对 Map 的一部分进行上锁. ConcurrentHashMap 当然可以代替 HashTable, 但是 HashTable 提供更强的线程安全性.
二, HashTable
1.HashTable 概述:
和 HashMap 一样, HashTable 也是一个散列表, 它存储的内容是键值对映射. HashTable 继承于 Dictionary, 实现了 Map,Cloneable,java.io.Serializable 接口. HashTable 的函数都是同步的, 这意味着它是线程安全的. 它的 Key,Value 都不可以为 null. 此外, HashTable 中的映射不是有序的.
HashTable 的实例有两个参数影响其性能: 初始容量和加载因子. 容量是哈希表中桶的数量, 初始容量就是哈希表创建时的容量. 注意, 哈希表的状态为 open: 在发生 "哈希冲突" 的情况下, 单个桶会存储多个条目, 这些条目必须按顺序搜索. 加载因子是对哈希表在其容量自动增加之前可以达到多满的一个尺度. 初始容量和加载因子这两个参数只是对该实现的提示. 关于何时以及是否调用 rehash 方法的具体细节则依赖于该实现. 通常, 默认加载因子是 0.75.
2.Hash Table 的数据结构:
HashTable 与 Map 关系如下
- public class Hashtable<K,V>
- extends Dictionary<K,V>
- implements Map<K,V>, Cloneable, java.io.Serializable
HashTable 并没有去继承 AbstractMap, 而是选择继承了 Dictionary 类, Dictionary 是个被废弃的抽象类.
3. 实现原理:
成员变量跟 HashMap 基本类似, 但是 HashMap 更加规范, HashMap 内部还定义了一些常量, 比如默认的负载因子, 默认的容量, 最大容量等.
- public Hashtable(int initialCapacity, float loadFactor) {// 可指定初始容量和加载因子
- if (initialCapacity <0)
- throw new IllegalArgumentException("Illegal Capacity:"+
- initialCapacity);
- if (loadFactor <= 0 || Float.isNaN(loadFactor))
- throw new IllegalArgumentException("Illegal Load:"+loadFactor);
- if (initialCapacity==0)
- initialCapacity = 1;// 初始容量最小值为 1
- this.loadFactor = loadFactor;
- table = new Entry[initialCapacity];// 创建桶数组
- threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);// 初始化容量阈值
- useAltHashing = sun.misc.VM.isBooted() &&
- (initialCapacity>= Holder.ALTERNATIVE_HASHING_THRESHOLD);
- }
- /**
- * Constructs a new, empty hashtable with the specified initial capacity
- * and default load factor (0.75).
- */
- public Hashtable(int initialCapacity) {
- this(initialCapacity, 0.75f);// 默认负载因子为 0.75
- }
- public Hashtable() {
- this(11, 0.75f);// 默认容量为 11, 负载因子为 0.75
- }
- /**
- * Constructs a new hashtable with the same mappings as the given
- * Map. The hashtable is created with an initial capacity sufficient to
- * hold the mappings in the given Map and a default load factor (0.75).
- */
- public Hashtable(Map<? extends K, ? extends V> t) {
- this(Math.max(2*t.size(), 11), 0.75f);
- putAll(t);
- }
--HashTable 的默认容量为 11, 默认负载因子为 0.75.(HashMap 默认容量是 16, 默认负载因子也是 0.75)
--HashTable 的容量可以为任意整数, 最小值为 1, 而 HashMap 的容量始终为 2 的 n 次方.
-- 为避免扩容带来的性能问题, 建议指定合理容量. 跟 HashMap 一样, HashTable 内部也有一个静态类叫 Entry, 其实是个键值对, 保存了键和值的引用. 也可以理解为一个单链表的节点, 因为其持有下一个 Entry 对象的引用.
4.HashTable 的存取实现:
HashTable 和 HashMap 存储的都是键值对对象, 而不是单独的键或值.
- public synchronized V put(K key, V value) {// 向哈希表中添加键值对
- // Make sure the value is not null
- if (value == null) {// 确保值不能为空
- throw new NullPointerException();
- }
- // Makes sure the key is not already in the hashtable.
- Entry tab[] = table;
- int hash = hash(key);// 根据键生成 hash 值 ---->若 key 为 null, 此方法会抛异常
- int index = (hash & 0x7FFFFFFF) % tab.length;// 通过 hash 值找到其存储位置
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {/ 遍历链表
- if ((e.hash == hash) && e.key.equals(key)) {// 若键相同, 则新值覆盖旧值
- V old = e.value;
- e.value = value;
- return old;
- }
- }
- modCount++;
- if (count>= threshold) {// 当前容量超过阈值. 需要扩容
- // Rehash the table if the threshold is exceeded
- rehash();// 重新构建桶数组, 并对数组中所有键值对重哈希, 耗时!
- tab = table;
- hash = hash(key);
- index = (hash & 0x7FFFFFFF) % tab.length;// 这里是取摸运算
- }
- // Creates the new entry.
- Entry<K,V> e = tab[index];
- // 将新结点插到链表首部
- tab[index] = new Entry<>(hash, key, value, e);// 生成一个新结点
- count++;
- return null;
- }
- public synchronized V get(Object key) {// 根据键取出对应索引
- Entry tab[] = table;
- int hash = hash(key);// 先根据 key 计算 hash 值
- int index = (hash & 0x7FFFFFFF) % tab.length;// 再根据 hash 值找到索引
- for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {// 遍历 entry 链
- if ((e.hash == hash) && e.key.equals(key)) {// 若找到该键
- return e.value;// 返回对应的值
- }
- }
- return null;// 否则返回 null
- }
--HashTable 并不允许值和键为空, 若为空, 则抛出空指针异常.
--HashMap 计算索引的方式是 h&(length-1), 而 HashTable 用的是模运算, 效率上是低于 HashMap 的.
--HashTable 计算索引时将 hash 值先与上 0x7fffffff, 这是为了保证 hash 值始终为整数.
--HashTable 中若干方法都添加了 synchronized 关键字, 也就意味着这个 HashTable 是个线程安全的类, 这是它与 HashMap 最大的不同点.
--HashTable 每次扩容都是旧容量的 2 倍加 2, 而 HashMap 为旧容量的 2 倍.
来源: http://www.jianshu.com/p/9ba71a619082