一、HashMap和HashTable的区别
HashMap和HashTable都实现了Map的接口，用哪个主要看他们的区别，主要体现在：线程安全，同步和速度上
区别如下
- HashMap可以接受为null的键值(key)和值(value)，（必须同时为null）而Hashtable则不行
- HashMap是非synchronized（同步），而Hashtable是synchronized。Hashtable是synchronized意味着多线程的环境下，某个线程对HashTable进行操作前要先对HashMap上锁，使用完之后解锁，一次仅有一个线程可以修改HashMap，这意味着Hashtable是线程安全的，多个线程可以共享一个Hashtable。而如果没有正确的同步的话，多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的扩展性更好。
- HashMap的迭代器是fail-fast的，fail-fast意味着在某个线程用过iterator去遍历集合的过程中，该集合的内容被另外一个线程修改了，那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。而Hashtable的enumerator迭代器不是fail-fast的
- HashMap不能保证随着时间的推移Map中元素的次序不改变
- 因为HashTable是线程安全也是synchronized的，所以在单线程的情况下，HashTable的速度是慢与HashMap的
二、HashMap和Treemap的区别
| TreeMap | HashMap | |
|---|---|---|
| 实现 | SortMap接口，基于红黑树 | 基于哈希散列表实现 |
| 存储 | 默认按键的升序排序 | 随机存储 |
| 遍历 | Iterator遍历是排序的 | Iterator遍历是随机的 |
| 损耗 | 插入、删除 | 基本无 （冲突的时候有） |
| 键值对 | 键、值都不能为null | 只允许键、值均为null |
| 安全 | 非并发安全Map | 非并发安全Map |
| 效率 | 低 | 高 |
TreeMap在插入元素的时候回进行平衡调节，所以在性能上会有损失
三、HashMap
1.HashMap的数据结构
Java中的数据结构基本可以用数组+链表的解决。
- 数组的优缺点:通过下标索引方便查找，但是在数组中插入或删除一个元素比较困难。
- 链表的优缺点:由于在链表中查找一个元素需要以遍历链表的方式去查找，而插入，删除快速。因此链表适合快速插入和删除的场景，不利于查找
而HashMap就是综合了上述的两种数据结构的优点，HashMap由Entry数组+链表组成，如下图所示:
1.png
2.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值，为了让分布更均匀），根据hash值得到这个元素在数组中的位置（即下标）， 如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。
3.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方法在对应位置的链表中找到需要的元素。
4.HashMap的resize（rehash）
HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率(不能让相同hash值对应的链表过长)，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。
那么HashMap什么时候进行扩容呢？当HashMap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过160.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍（每次扩充必须是2的倍数），然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。
5.HashMap的遍历方式
高效（entry就是存放键值对的数组）
Map map = new HashMap();
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}
低效（因为要再做一次哈希）
Map map = new HashMap();
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
Object key = iter.next();
//下面要再做一次哈希
Object val = map.get(key);
}
6.相关问题
- 新调整HashMap大小存在什么问题吗？：多线程情况下可能产生条件竞争
- 可能遇到的bucket概念：bucket即某个hash值对应的存储空间，可能是单个键值对，也可能使键值对链
- 可以使用自定义的对象作为键吗：只要它遵守了equals()和hashCode()方法的定义规则，并且当对象插入到Map中之后将不会再改变了。如果这个自定义对象时不可变的，那么它已经满足了作为键的条件，因为当它创建之后就已经不能改变了。
- 可以使用CocurrentHashMap来代替Hashtable吗：Hashtable是synchronized的，但ConcurrentHashMap同步性能更好，因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable，但是HashTable提供更强的线程安全性。
网友评论