李文轩 2019-03-30
声明：这是本人学习极客时间的Java核心36讲的笔记，有侵权请联系我。
Hashtable、HashMap、TreeMap
都是
Map的实现，以键值对的形式存储和操作数据的容器类型Hashtable是哈希表的实现，是同步的，性能开销比较大；具备无序特性；不支持null键和值HashMap也是哈希表的实现，不是同步的，所以比较常用；具备无序特性；支持null键和值；put和get操作都达到常数时间的性能TreeMap是基于红黑树的一种提供顺序访问的Map；get、put、remove之类的基本操作都是O(log(n))的时间复杂度。具体顺序由Comparator或键的自由顺序决定；所以一般需要排序对情况下是选择它。默认升序排序方式。当未实现Comparator或在实现中未对null情况进行判断时，key不能为null。同样是可以保证某种顺序，
LinkedHashMap通常提供的是遍历顺序符合插入顺序，它的实现是通过为键值对维护一个双向链表
线程安全（来自评论区）
- HashMap本身是不支持同步的；Hashtable因为通过阻塞状态的方式，所以在多线程下也会效率低下
- 建议可以使用
Collection的synchronizedMap方法 或者ConcurrentHashMap类-
ConcurrentHashMap类是基于lock实现锁分段 - 将Map存放的数据分成一段一段的存储方式，然后给每一段数据分配一把锁，当一个线程占用锁访问其中一个段的数据时，其他段的数据也能被其他线程访问。
- ConcurrentHashMap不仅保证了多线程运行环境下的数据访问安全性，而且性能上有长足的提升。
-
Map 整体结构
Hashtable比其他Map要不同，它是扩展了Dictionary类的其他
Map都是扩展类AbstractMap的，里面包含类通用方法抽象。设计目的一句体现在不用接口上。大部分
Map的使用场景都是，放入、访问或者删除，对顺序没有要求；HashMap的性能较好，它是一般情况的最好选择。-
HashMap的性能依赖于哈希值的有效性：-
equals相等，hashCode一定也要相等 - 重写了
hashCode也要重写equals -
hashCode需要保持一致性，状态改变返回的哈希值仍然要一致 -
equals的对称、反射、传递等特性 -
compareTo的返回值需要和equals一致，否则会出香模凌两可的情况
-
LinkedHashMap通过特定构造函数，可以创建反映访问顺序的实例比如如果想建造一个空间敏感的资源池，我们希望在新资源加入时，同时释放最不常用的一个数据
import java.util.LinkedHashMap;
import java.util.Map;
public class LinkedHashMapSample {
public static void main(String[] args) {
LinkedHashMap<String, String> accessOrderedMap = new LinkedHashMap<String, String>(16, 0.75F, true){
@Override
protected boolean removeEldestEntry(Map.Entry<String, String> eldest) { // 实现自定义删除策略，否则行为就和普遍 Map 没有区别
return size() > 3;
}
};
accessOrderedMap.put("Project1", "Valhalla");
accessOrderedMap.put("Project2", "Panama");
accessOrderedMap.put("Project3", "Loom");
accessOrderedMap.forEach( (k,v) -> {
System.out.println(k +":" + v);
});
// 模拟访问
accessOrderedMap.get("Project2");
accessOrderedMap.get("Project2");
accessOrderedMap.get("Project3");
System.out.println("Iterate over should be not affected:");
accessOrderedMap.forEach( (k,v) -> {
System.out.println(k +":" + v);
});
// 触发删除
accessOrderedMap.put("Project4", "Mission Control");
System.out.println("Oldest entry should be removed:");
accessOrderedMap.forEach( (k,v) -> {// 遍历顺序不变
System.out.println(k +":" + v);
})
}
}
- 这段代码限制了资源池size为3，当“project4“加入时，同时删除了”project1“
HashMap源码
-
HashMap内部实现基本点
- 可以看作一个数组和链表结合的复合结构，数组被分为桶（bucket）
- 用哈希值决定了键值对属于哪个桶
-
容量（
capacity)和负载系数（load factor）。- 容量理论最大极限由
MAXIMUM_CAPACITY指定，数值为2的30次方 - 在源码的
putVal方法里可以看出，resize方法处理了几个问题：- 在表格是null的时候，
resize方法会负责初始化 -
resize也负责扩容；新插入的键值对会检查++size > threshold；若true，则调用resize
- 在表格是null的时候，
- 门阀值
threshold等于（负载因子）*（容量），判断是否扩容的关键 - 门阀值通常以倍数调整，当元素数量超过门阀值时，调整
Map大小。 - 而容量和负载因子决定了可用的桶的数量；若只使用一个桶，
HashMap会退回链表的状态
- 容量理论最大极限由
-
树化
- 逻辑主要存在于
putVal和treeifyBin中 - 主要注意的是，如果桶里的元素数量大于
TREEIFY_THRESHOLD- 如果容量小于
MIN_TREEIFY_CAPACITY，只会进行简单扩容 - 如果容量大于
MIN_TREEIFY_CAPACITY，则是进行树化改造
- 如果容量小于
- 树化大主要原因是安全问题，若大部分键值对处于一个bin中，则会形成一个链表
- 构造哈希冲突从而导致服务器CPU大量占用（链表查询为线性，严重影响存取）是比较简单的攻击手段
- 逻辑主要存在于
重写 hashCode 和 equals 方法
如果我们要将自定义类当作键加入到
HashMap中，如果不重写，结果可能和我们预想的不太一样如果我们没有重写自定义对象的
hashCode方法，在作为键加入到HashMap里时调用hashCode方法的时候，程序将调用Object里的hashCode方法，即返回对象的内存地址。这并不是我们所期待的。重写可以调用
Object.hash(Object...values)方法，或xx.hashCode()如果我们没有重写自定义对象的
equals方法，即使我们用同样哈希值去找HashMap里的值的时候，get会返回null。因为我们没有重写equals的话，程序自动调用Object里的equals方法；这个固定方法是比较键的内存地址的，所以即使用同样的哈希值的不同对象，返回的依然是null。重写可以先检查是否是null对象和是否同一类型的对象。如果不是null和是同一类型，那么可以逐个对比两个对象里的成员变量
两个
equals返回true的对象一定有一样的hashCode，但是两个有相同hashCode的对象不一定equals返回true。因为hashCode其实作为一个对象存储的参数存在于对象中，有可能两个对象有相同的hashCode，但是他们的成员变量不一定都是相等；一定是所以成员变量相等和同一对象类型的两个对象才相等。
