前言
Map为一个Java中一个重要的数据结构，主要表示<key, value>的映射关系对。本文包括了相关Map数据结构的总结和源码的阅读注释。
HashMap
初始化，可以选择第二个初始化函数来设置装载能力threshold和装载系数loadFactor：
HashMap()HashMap(int initialCapacity, float loadFactor)
HashMap中定义的一些常量：
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;缺省的初始大小
static final int MAXIMUM_CAPACITY = 1 << 30;最大限定大小，当超过这个值时，会
resize()到Integer.MAX_VALUEstatic final float DEFAULT_LOAD_FACTOR = 0.75f;threshold = capacity*laodFactor
HashMap的大小始终为2的倍数，若插入时超过threshold时，会调用resize()来自动将大小扩大一倍。
值在Node<K,V>[] table中的定位方式为(n-1)&hash(key)，这也是resize的时候直接double的原因
基本方法：
V put(K key, V value)：若key不存在，则插入；若key存在，则更新value值，返回旧的valueV putIfAbsent(K key, V value)V get(Object key)：get不存在的key时会返回null，需要注意NullPointerExceptionint size()
遍历方式
forEach(lambda)通过lambda表达式进行遍历entrySet().iterator()Iterator iter = map.entrySet().iterator(); while(iter.hasNext()){ Map.Entry e = (Map.Entry)iter.next(); key = e.getKey(); value = e.getValue(); }keySet().iterator()Iterator iter = map.keySet().iterator(); while(iter.hasNext()){ key = iter.next(); value = map.get(key); }values().iterator()
resize()
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) { // 旧的大小已经达到设置的最大值时不再增加，改变阈值
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && // 新大小=旧大小*2
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 阈值也一起*2
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // oldCap为0时处于初始化阶段，进行初始化
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) { // 将旧map移到新map中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null; // 置为null值方便GC
if (e.next == null) // 桶中没有链，直接赋值
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) // 如果桶中为红黑树
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) { // 若为真，则在原来位置不变
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { // 为假时说明扩容后原链表中的节点位置发生了改变
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead; // 原链表所在
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead; // 扩容部分节点位置加上了oldCap
}
}
}
}
}
return newTab;
}冲突解决
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; // 数组为空的情况
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); // 没有冲突直接放入
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 有冲突但是key相同，则覆盖原来的值
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 如果已经拉成红黑树则插入树中
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null); // 找到链表尾插入链表中
if (binCount >= TREEIFY_THRESHOLD - 1) // 如果桶的链长度超过阈值则拉成红黑树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break; // 在链中找到相同的key则覆盖其值
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}Hashtable
初始化函数：
public Hashtable() {
this(11, 0.75f);
}默认下initialCapacity = 11，loadFactor = 0.75。
插入操作put(K,V)
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 = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) { // 找到相同的key则覆盖原值
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}Hashtable的hash寻址方法为(hash & 0x7FFFFFFF) % tab.length，当插入的key之前有值时返回旧值，否则返回null。
addEntry(hash, key, value, index)，当table的大小不够时，执行rehash()扩大table
private void addEntry(int hash, K key, V value, int index) {
Entry<?,?> tab[] = table;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
modCount++;
}rehash():
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1; // 新大小=原大小*2+1
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); // 更新阈值
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) { // 将旧map中的值一道新map
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}与HashMap的区别
HashMap 继承自AbstractMap类，Hashtable继承自Dictionary类
- Hashtable中的方法均用sychronized关键字修饰，为线程安全
- 扩容方法不同，HashMap直接double，使得大小始终是2的倍数，Hashtable在double后加1
在table中的查找方式不同：HashMap为
hash&(n-1)，Hashtable为(hash & 0x7FFFFFFF) % tab.length
TreeMap
TreeMap的本质是红黑树，红黑树是一种特殊的二叉查找树，所以TreeMap中的节点都是有序的。
TreeMap中节点Entry的定义为
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;
}初始化函数：
public TreeMap() {
comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}TreeMap支持自定义的比较器，若是使用空初始化函数，则默认为key的自然顺序
/**
* The comparator used to maintain order in this tree map, or
* null if it uses the natural ordering of its keys.
*
* @serial
*/
private final Comparator<? super K> comparator;插入操作put(K,V)
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) { // root为空则直接new
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) { // 自定义comparator时
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value); // 如果key相等则直接覆盖value
} while (t != null);
}
else { // 使用key的comparable接口
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value); //找到相同的key则直接覆盖value返回
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent); // 插入节点
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e); // 红黑树自平衡过程
size++;
modCount++;
return null;
}插入后红黑树的自平衡过程:
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED; // 设插入节点的颜色为红
while (x != null && x != root && x.parent.color == RED) { // 当x.parent为黑时树已经平衡
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { // x.parent是祖父节点的左子节点
Entry<K,V> y = rightOf(parentOf(parentOf(x))); // x的uncle节点
if (colorOf(y) == RED) { // uncle为红的时候recolor
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x)); // 向上变色直到满足平衡条件
} else { // uncle为黑的时候则需要rotate
if (x == rightOf(parentOf(x))) { // 左右的情况，向左旋转
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) { // 右左的情况，向右旋转
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}如有不对请多指正
