1 Map集合类型
1.1 Map
- 特点：存储的键值对映射关系，根据key可以找到value
- Map中所有的Key集合可以看做Set集合，无序、唯一
- Map中所有Value的集合无序、不唯一
- Set集合的底层就是Map，所以Set和Map的类型一致，也有HashMap、LinkedHashMap、TreeMap三种
1.2 HashMap
• 采用Hashtable哈希表存储结构
• 优点：添加速度快 查询速度快 删除速度快
• 缺点：key无序
1.3 LinkedHashMap
• 采用哈希表存储结构，同时使用链表维护次序
• key有序（添加顺序）
1.4 TreeMap
• 采用二叉树（红黑树）的存储结构
• 优点：key有序 查询速度比List快
• 缺点：查询速度没有HashMap快
2 Map接口方法摘要
| 返回值 | 方法描述 |
|---|---|
| void | clear() 从此映射中移除所有映射关系（可选操作）。 |
| boolean | containsKey(Object key) 如果此映射包含指定键的映射关系，则返回 true。 |
| boolean | containsValue(Object value) 如果此映射将一个或多个键映射到指定值，则返回 true。 |
| Set<Map.Entry<K,V>> | entrySet() 返回此映射中包含的映射关系的 Set 视图。 |
| boolean | equals(Object o) 比较指定的对象与此映射是否相等。 |
| V | get(Object key) 返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回 null。 |
| int | hashCode() 返回此映射的哈希码值。 |
| boolean | isEmpty() 如果此映射未包含键-值映射关系，则返回 true。 |
| Set | keySet() 返回此映射中包含的键的 Set 视图。 |
| V | put(K key, V value) 将指定的值与此映射中的指定键关联（可选操作）。 |
| void | putAll(Map<? extends K,? extends V> m) 从指定映射中将所有映射关系复制到此映射中（可选操作）。 |
| V | remove(Object key) 如果存在一个键的映射关系，则将其从此映射中移除（可选操作）。 |
| int | size() 返回此映射中的键-值映射关系数。 |
| Collection | values() 返回此映射中包含的值的 Collection 视图。 |
3 HashMap源码分析
- JDK1.7及其之前，HashMap底层是一个table数组+链表实现的哈希表存储结构
- 在JDK1.8中有一些变化，当链表的存储数据个数大于等于8的时候，不再采用链表存储，而采用红黑树存储结构。这么做主要是查询的时间复杂度上，链表为O(n)，而红黑树一直是O(logn)。如果冲突多，并且超过8，采用红黑树来提高效率
- 链表的每个节点就是一个Entry，其中包括：键key、值value、键的哈希码hash、执行下一个节点的引用next四部分
static class Entry<K, V> implements Map.Entry<K, V> { final K key; //key V value;//value Entry<K, V> next; //指向下一个节点的指针 int hash;//哈希码 }
3.1 HashMap基本属性
//JDK1.7
public class HashMap<K, V> implements Map<K, V> {
//哈希表主数组的默认长度
static final int DEFAULT_INITIAL_CAPACITY = 16;
//默认的装填因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//主数组的引用
transient Entry<K, V>[] table;
int threshold;//界限值 阈值 主数组长度×装填因子
final float loadFactor;//装填因子
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
this.loadFactor = loadFactor;//0.75
threshold = (int) Math.min(capacity * loadFactor,
MAXIMUM_CAPACITY + 1);//16*0.75=12
table = new Entry[capacity];
....
}
}
3.2 HashMap的put方法
调用put方法添加键值对。哈希表主要通过三个步骤添加数据：
- 第一步计算哈希码，注意计算哈希码时不仅调用了key的hashCode()，还进行了更复杂处理，目的是尽量保证不同的key尽量得到不同的哈希码
- 第二步根据哈希码计算存储位置，这里使用了位运算提高效率。同时也要求主数组长度必须是2的幂
- 第三步添加Entry
正常情况：添加到链表的第一个位置，而不是链表末尾
发现了相同的key已经存在的情况：就使用新的value替代旧的value，并且返回旧的value
public class HashMap {
public V put(K key, V value) {
//如果key是null，特殊处理
if (key == null) return putForNullKey(value);
//1.计算key的哈希码hash
int hash = hash(key);
//2.将哈希码代入函数，计算出存储位置 y= x%16；
int i = indexFor(hash, table.length);
//如果已经存在链表，判断是否存在该key，需要用到equals()
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如找到了,使用新value覆盖旧的value，返回旧value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;// the United States
e.value = value;//America
e.recordAccess(this);
return oldValue;
}
}
//添加一个结点
addEntry(hash, key, value, i);
return null;
}
final int hash(Object k) {
int h = 0;
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
//作用就相当于y = x%16,采用了位运算，效率更高
return h & (length-1);
}
}
3.3 HashMap的get方法
其实是根据key找Entry，再从Entry中获取value即可
public V get(Object key) { //根据key找到Entry（Entry中有key和value） Entry<K,V> entry = getEntry(key); //如果entry== null,返回null，否则返回value return null == entry ? null : entry.getValue(); }
3.4 HashMap的扩容
void addEntry(int hash, K key, V value, int bucketIndex) {
//如果达到了门槛值，就扩容，容量为原来容量的2位 16---32
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//添加节点
createEntry(hash, key, value, bucketIndex);
}
4 TreeMap源码分析
TreeMap每个节点的结构
static final class Entry<K,V> implements Map.Entry<K,V> { K key; V value; Entry<K,V> left; Entry<K,V> right; Entry<K,V> parent; boolean color = BLACK; }
4.1 TreeMap基本属性
public class TreeMap<K, V> implements NavigableMap<K, V> {
private final Comparator<? super K> comparator;//外部比较器
private transient Entry<K, V> root = null; //红黑树根节点的引用
private transient int size = 0;//红黑树中节点的个数
public TreeMap() {
comparator = null;//没有指定外部比较器
}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;//指定外部比较器
}
}
4.2 TreeMap的put和get方法
添加原理
- 从根节点开始比较
- 添加过程就是构造二叉平衡树的过程，会自动平衡
- 平衡离不开比较：外部比较器优先，然后是内部比较器。如果两个比较器都没有，就抛出异常
- 查找方法与添加方法的原理基本相同
public V put(K key, V value) {
Entry<K,V> t = root;
//如果是添加第一个节点，就这么处理
if (t == null) {
//即使是添加第一个节点，也要使用比较器
compare(key, key); // type (and possibly null) check
//创建根节点
root = new Entry<>(key, value, null);
//此时只有一个节点
size = 1;
return null;
}
//如果是添加非第一个节点，就这么处理
int cmp;
Entry<K,V> parent;
Comparator<? super K> cpr = comparator;
//如果外部比较器存在，就使用外部比较器
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;//在左子树中查找
else if (cmp > 0)
t = t.right; //在右子树查找
else
//找到了对应的key，使用新的value覆盖旧的value
return t.setValue(value);
} while (t != null);
}
else {
//如果外部比较器没有，就使用内部比较器
....
}
//找到了要添加的位置，创建一个新的节点，加入到树中
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
size++;
return null;
}
public V get(Object key) {
//根据key（cn）找Entry（cn--China）
Entry<K,V> p = getEntry(key);
//如果Entry存在，返回value：China
return (p==null ? null : p.value);
}
final Entry<K, V> getEntry(Object key) {
//如果外部比较器存在，就使用外部比较器
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
//如果外部比较器不存在，就使用内部比较器
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K, V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
//如果找到了，就返回Entry
return p;
}
//如果没有找到，就返回null
return null;
}