Map接口
- 将键映射到值的对象，一个映射不能包含重复的键；每个键最多只能映射到一个值。
- Map 接口提供三种 collection 视图，允许以键集、值集或键-值映射关系集的形式查看某个映射的内容。
- 映射顺序定义为迭代器在映射的 collection 视图上返回其元素的顺序。某些 Map 实现可明确保证其顺序，如 TreeMap 类；另一些Map实现则不保证顺序，如 HashMap 类。
- 某些Map实现对可能包含的键和值有所限制。例如，某些实现禁止 null 键和值，另一些则对其键的类型有限制。
AbstractMap 抽象类
实现了Map中的绝大部分函数接口。它减少了“Map的实现类”的重复编码。
具体实现类
HashMap
类声明如下
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, SerializableHashMap 也是我们使用非常多的容器，它是基于哈希表的 Map 接口的实现，以key-value的形式存在。
在介绍构造函数之前，先介绍几个简单的概念
- 散列（Hash）表：是根据关键字而直接进行访问的数据结构，也就说，散列表建立了关键字和存储地址之间的映射关系。从散列表的结构特性上可以看出，特别适合用来实现 Map 接口。
- 散列函数 Hash(key) = Address , 即可以通过 key 来定位到元素的存储位置。
- 冲突，任何三散列函数都不可能绝对避免冲突，冲突指 Hash（key1） = Hash（key2）这种情况，即多个 key 通过散列函数被映射到同一个位置，key1 key2 称作同义词。
- 拉链法，把所有的同义词存储在一个线性链表中，这个线性链表有散列地址（Hash(key) ）唯一标示。HaspMap就是通过散列表这种数据结构进行实现，利用拉链法解决冲突的。
- 负载因子，（负载因子=表中的记录数/散列表的长度），负载因子越大，散列表越满，发生冲突的几率越大。HashMap 默认的负载因子为 0.75 ,HashMap 添加键值对时会不断计算当前的负载因子，一旦负载因子大于 0.75 那么必须对散列表进行扩容。重新 Hash 每一个元素，是一件非常费时的操作，所以在创建 HashMap 时指定合适的容量是一个不错的选择。
上面简单介绍了 HashMap 所涉及的几个概念，后面会详细介绍 HashMap 是怎样使用和实现这些概念的。
HashMap 的成员属性
static final int DEFAULT_INITIAL_CAPACITY = 16;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient Entry[] table;
transient int size;
int threshold;
final float loadFactor;
transient volatile int modCount;DEFAULT_INITIAL_CAPACITY ：默认 HashMap 容器的容量
MAXIMUM_CAPACITY ： HashMap 容器最大容量
DEFAULT_LOAD_FACTOR ： HashMap 默认的负载因子
size： 容器中有效元素的个数
threshold：容器中成员属性 table 数组的长度与 loadFactor 的乘积，即容器需要扩容的界限。
loadFactor：负载因子
Entry[] table：table 是HashMap中比较关键的一个成员属性，先看一下数组的类型 Entry
static class Entry<K, V> implements Map.Entry<K, V> {
final K key;
V value;
Entry<K, V> next;
final int hash;
Entry(int h, K k, V v, Entry<K, V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry) o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return (key == null ? 0 : key.hashCode())
^ (value == null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
void recordAccess(HashMap<K, V> m) {
}
void recordRemoval(HashMap<K, V> m) {
}
}Entry 类保存键值对的 key 值，value 值，key 的 hashcode 值和下一个 Entry 的引用。这就是上面所说的拉链法就是通过 table 属性和 Entry 类实现的。HashMap 在添加一个键值对 entry1 = < key1 ， value1 >的时候，首先计算 key1 hash 值。假设 hash（key1）= 2，那么设置 table[2] = value1 。接下来添加键值对 entry2 =< key2 ， value2 >的时候，假设 hash（key1）= 2，那么此时就产生冲突了，所以需要用拉链法解决，即 entry1.next = entry2 。
HashMap 的构造方法
Constructor 1
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}Constructor 1：
设定 hashMap 的容负载因子为 0.75
设定 hashMap.threshold 当前允许添加元素的个数
初始化长度 16 的数组 table ，但是这个长度值跟容器 size 不是一回事，与 threshold 也不是一回事。
Constructor 2
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}Constructor 2
直接调用 Constructor 3
Constructor 3
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}跟 Constructor 1 差不多，只有一个地方需要注意
while (capacity < initialCapacity)
capacity <<= 1;HashMap 默认的初始化长度为 16 = 2^4 ，在指定长度的时候，HashMap 仍然会选择一个 2 的整数倍的值。这样做的目的是为了后面进行 hashcode 计算。
Constructor 4
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
putAllForCreate(m);
}调用 Constructor 3
接下来看一下 HashMap 类元素增加、删除、访问和迭代实现的具体细节
1 添加元素
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
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;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}首先观察到 HashMap 是允许 key=null 元素（此处所指的元素均代表 Entry 对象）加入的，通过 putForNullKey 方法添加。
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}默认将 null 元素方法在 table[0] 处，或则 table[0] 连接的链表中。如果应经存在 key == null 的元素，那么覆盖原来的元素 value 值。否则新增一个元素。
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}新建一个 Entry 对象，并复制给 table[0]，然后判断 HashMap 中有效元素数量是否已将达到上限，若达到，马上进行扩展，扩展的过程会在后面讲述。
接着往下将 put 方法中的其他内容
int hash = hash(key.hashCode());
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}hash 方法可以进一步修正 key 的 hashcode 值，降低冲突的发生几率，但是函数背后的数学意义我不清楚，待以后慢慢修正，下一步需要根据修正后的 hash 去确定该元素的准确位置，即 Hash(key) == Address的过程，具体方法如下：
static int indexFor(int h, int length) {
return h & (length-1);
}HashMap 的底层数组长度总是 2 的 n 次方，在构造函数中存在：capacity <<= 1;这样做总是能够保证HashMap 的底层数组长度为 2 的 n 次方。当 length 为 2 的 n 次方时，h&(length – 1) 就相当于对 length取模，而且速度比直接取模快得多，这是 HashMap 在速度上的一个优化。至于为什么是2的n次方下面解释。
h&(length – 1)，这句话除了上面的取模运算外还有一个非常重要的责任：均匀分布table数据和充分利用空间。这里我们假设length为 16(2^n) 和 15 ，h 为 5、6、7。
当n=15时，6和7的结果一样，这样表示他们在table存储的位置是相同的，也就是产生了碰撞，6、7就会在一个位置形成链表，这样就会导致查询速度降低。诚然这里只分析三个数字不是很多，那么我们就看0-15。
从上面的图表中我们看到总共发生了8此碰撞，同时发现浪费的空间非常大，有1、3、5、7、9、11、13、15处没有记录，也就是没有存放数据。这是因为他们在与14进行&运算时，得到的结果最后一位永远都是0，即0001、0011、0101、0111、1001、1011、1101、1111位置处是不可能存储数据的，空间减少，进一步增加碰撞几率，这样就会导致查询速度慢。而当length = 16时，length – 1 = 15 即1111，那么进行低位&运算时，值总是与原来hash值相同，而进行高位运算时，其值等于其低位值。所以说当length = 2^n时，不同的hash值发生碰撞的概率比较小，这样就会使得数据在table数组中分布较均匀，查询速度也较快。
接下来就是加入元素的逻辑了
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;
}
}我们这里假设 value = m，key = III，i = 2，目前 HashMap 容器的存储情况如下：
Jdk 对于一个对象的 equals 和 hashcode 方法有如下的规定：
如两个对象 equals 方法返回 true,那么这两个对象的 hashcode 方法必须返回相同的值，若 equlas 方法返回 false，那么这两个对象的 hascode 方法可以返回相同值，也可以返回不同的值。也就说，若两个对象的 hashcode 方法返回不同的值，那么两个对象肯定是不 equals的，如果两个对象的 hashcode 方法返回的值相同，也不能确定这两个对象是 equals的
从 table[2] 对象开始循环遍历整个链表，若 hashcode 值一样，那么还不能确定两个 key 是相等的，继续 (k = e.key) == key || key.equals(k)) 判定。也许会有人有疑问，为什么这么费事，直接比较 equals 方法不就好吗？为什么还要先进行 hashcode 的比较呢？
有些时候某些类的 equals 方法比较复杂，需要耗费很长时间计算，而如果两个对象的 hashcode 值不同，就可以直接判定两个对象不 equals ,无需后续的 equals判定了。
按照上述的假设和规定，在 table[2] 处没有找到相同的 key（若找到直接覆盖原来的 vlaue），继续执行以下代码。
modCount++;
addEntry(hash, key, value, i);
return null;void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}加入新元素后， HashMap 当前的存储情况如下：
加入元素时，牵扯到一个扩容的问题，而且 HashMap 的扩容是一个非常费时的操作，因为扩容的目标是增加容器数组的长度，table.length 变化时，需要重新计算每一个元素的 hascode，从新定位元素在容器中的位置，resize 方法定义如下
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}HashMap 允许加入 key = null 的键值对
HashMap 未对加入的元素进行排序
HashMap 未提供线程同步机制
2 删除元素
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final Entry<K,V> removeEntryForKey(Object key) {
int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}删除元素与加入元素的逻辑基本一致，计算 key 的 hash 值，从 table[hash]开始检索，检索到 kye，删除 HashMap 中相应的元素。
3 访问元素
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;
}get 访问元素代码基本上都在前面出现过，这里就不在描述了。
4 迭代遍历
HashMap 提拱了三种 Collection 视图，允许以键集、值集或键-值集的形式查看 HashMap 的内容。分被对应以下方法和成员属性
- 键-值集
private transient Set<Map.Entry<K,V>> entrySet = null;
public Set<Map.Entry<K,V>> entrySet() {
return entrySet0();
}- 值集
transient volatile Collection<V> values = null;
public Collection<V> values() {
Collection<V> vs = values;
return (vs != null ? vs : (values = new Values()));
}- 键集
transient volatile Set<K> keySet = null;
public Set<K> keySet() {
Set<K> ks = keySet;
return (ks != null ? ks : (keySet = new KeySet()));
}首先从键-值集开始介绍
public Set<Map.Entry<K,V>> entrySet() {
return entrySet0();
}
private Set<Map.Entry<K,V>> entrySet0() {
Set<Map.Entry<K,V>> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
}
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return newEntryIterator();
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K,V> e = (Map.Entry<K,V>) o;
Entry<K,V> candidate = getEntry(e.getKey());
return candidate != null && candidate.equals(e);
}
public boolean remove(Object o) {
return removeMapping(o) != null;
}
public int size() {
return size;
}
public void clear() {
HashMap.this.clear();
}
}最终返回 EntrySet 类型的 Set 容器，那么我们看一下其中的 iterator 方法
public Iterator<Map.Entry<K,V>> iterator() {
return newEntryIterator();
}
Iterator<Map.Entry<K,V>> newEntryIterator() {
return new EntryIterator();
}
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() {
return nextEntry();
}
}
private abstract class HashIterator<E> implements Iterator<E> {
Entry<K,V> next; // next entry to return
int expectedModCount; // For fast-fail
int index; // current slot
Entry<K,V> current; // current entry
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
public final boolean hasNext() {
return next != null;
}
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
}HashIterator 类的构造方法中，遍历 table 数组，寻找到第一个 table[index] != null 的位置。成员变量 next 指向此位置。 next（）方法返回一个 Map.Entry类型的对象。下面用图片的形式展现 键-值 集的迭代过程。
测试用例代码如下：
public static void main(String[] args) throws InterruptedException {
HashMap<Integer,Character> hs = new HashMap<Integer,Character>();
hs.put(9, 'i');
hs.put(8, 'h');
hs.put(7, 'g');
hs.put(6, 'f');
hs.put(5, 'e');
hs.put(4, 'd');
hs.put(3, 'c');
hs.put(2, 'b');
hs.put(1, 'a');
hs.put(null, '0');
Set<Entry<Integer, Character>> sets = hs.entrySet();
for(Entry<Integer, Character> entry : hs.entrySet()){
System.out.println(entry.getValue());
}
}输出结果为
0
a
b
c
d
e
f
g
h
i
下面的截图是断点查看 table 数组中的 Entry
关于其他两种视图，这里就不在一一描述。
HashMap 总结
- HashMap 没有提供同步机制
- HashMap 底层是通过散列表实现的，利用拉链法解决冲突
- HashMap 允许 key = null 的元素加入
- HashMap 允许 vlaue = null 的元素加入
- HashMap 加入元素时没有进行排序
- HashMap 提供了三种 Collection 类型的视图
- HashMap 继承自 AbstractMap
Hashtable
Hashtable类声明如下
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable 可以看出 Hashtable 继承 Dictionary 类，实现 Map 接口。其中 Dictionary 类是任何可将键映射到相应值的类的抽象父类。
Hashtable 构造函数
Constructor 1
public Hashtable() {
this(11, 0.75f);
}Constructor 2
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}Constructor 3
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;
this.loadFactor = loadFactor;
table = new Entry[initialCapacity];
threshold = (int)(initialCapacity * loadFactor);
}Constructor 4
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}四个构造方法与 HashMap 基本一致，不再赘述
1 Hashtable 底层也是散列表结构，利用拉链法解决冲突
下面看一下 Hashtable 的增加、删除、访问和迭代方法
1 增加元素
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;
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;
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
Entry<K, V> e = tab[index];
tab[index] = new Entry<K, V>(hash, key, value, e);
count++;
return null;
}
put 方法与 HashMap 中的 put 方法逻辑基本一致，但是有以下个不同的地方：
if (value == null) {
throw new NullPointerException();
}Hashtable 不允许 value=null
Hashtavle 不允许 key = null ,调用 key.hashCode() 方法会出现空指针异常
Hashtavle 提供了同步机制
2 删除元素
public synchronized V remove(Object key) {
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K, V> e = tab[index], prev = null; e != null; prev = e, e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
count--;
V oldValue = e.value;
e.value = null;
return oldValue;
}
}
return null;
}remove 操作没有特别之处，不再赘述。
3 访问元素
public synchronized V get(Object key) {
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K, V> e = tab[index]; e != null; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
return null;
}int hash = key.hashCode()，从这里也可以看出，Hashtable 是不允许 key = null 的元素加入的。
4 迭代容器
Hashtable 同样提供了三个 Collection 视图
private transient volatile Set<K> keySet = null;
private transient volatile Set<Map.Entry<K,V>> entrySet = null;
private transient volatile Collection<V> values = null;获取视图的方法
public Set<K> keySet() {
if (keySet == null)
keySet = Collections.synchronizedSet(new KeySet(), this);
return keySet;
}
public Set<Map.Entry<K,V>> entrySet() {
if (entrySet==null)
entrySet = Collections.synchronizedSet(new EntrySet(), this);
return entrySet;
}
public Collection<V> values() {
if (values==null)
values = Collections.synchronizedCollection(new ValueCollection(),this);
return values;
}
下面以 keySet 为例进行介绍
public Set<K> keySet() {
if (keySet == null)
keySet = Collections.synchronizedSet(new KeySet(), this);
return keySet;
}Collections.synchronizedSet 方法可以把 Set 包装成一个线程安全的 Set ，接下来看一下 KeySet 类的定义
private class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return getIterator(KEYS);
}
public int size() {
return count;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return Hashtable.this.remove(o) != null;
}
public void clear() {
Hashtable.this.clear();
}
}键集 返回一个 Hashtable.KeySet 类型的集合，接下来看一下该集合的 iterator 方法
public Iterator<K> iterator() {
return getIterator(KEYS);
}
private <T> Iterator<T> getIterator(int type) {
if (count == 0) {
return (Iterator<T>) emptyIterator;
} else {
return new Enumerator<T>(type, true);
}
}
如果 Hashtable 容器没有有效元素则返回一个 EmptyEnumerator 类型的迭代器，如不为空则返回一个 Enumerator 类型的迭代器，下面我们看一下 Enumerator 迭代器的类型声明
private class Enumerator<T> implements Enumeration<T>, Iterator<T>实现了 Iterator 和 Enumeration 接口，那么可以有两种方式来迭代遍历键集，如下所示
public static void main(String[] args) throws InterruptedException {
Hashtable<Integer,Character> ht = new Hashtable<Integer,Character>();
ht.put(1, 'a');
Collection<Integer> keys = ht.keySet();
Iterator<Integer> iterator = keys.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
Enumeration<Integer> enumerator = (Enumeration<Integer>) keys.iterator();
while(enumerator.hasMoreElements()){
System.out.println(enumerator.nextElement());
}
}Hashtable有两种迭代方式
Hashtable 总结
- Hashtable 提供同步机制
- Hashtable 不允许 key = null
- Hashtable 不允许 value = null
- Hashtable 底层由散列表数据结构实现，利用拉链法解决冲突问题
- Hashtable 元素插入的时候没有进行排序
- Hashtable 提供三种 Colletion 类型的视图
TreeMap
- 底层基于红黑树算法实现的
- TreeMap 可以根据元素键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序。
- 实现 NavigableMap 接口，提供一系列的导航方法，具备针对给定搜索目标返回最接近匹配项的导航方法 。方法 lowerEntry、floorEntry、ceilingEntry 和 higherEntry 分别返回与小于、小于等于、大于等于、大于给定键的键关联的 Map.Entry 对象，如果不存在这样的键，则返回 null。
TreeMap 类声明
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.SerializableTreeMap 构造函数
Constructor 1
public TreeMap() {
comparator = null;
}Constructor 2
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}Constructor 2
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}Constructor 3
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}Constructor 4
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}TreeMap 成员属性
private transient int size = 0;
private transient int modCount = 0;
private final Comparator<? super K> comparator;
private transient Entry<K,V> root = null;size ： 记录 TreeMap 中的有效元素
modCount ：记录 TreeMap 被结构化修改的次数
Comparator ： 记录 TreeMap 比较器，通过 Comparator.compare（key1，key2) 对元素进行排序
Entry ： TreeMap 底层红黑树节点的类型，即 TreeMap 元素的类型
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left = null;
Entry<K,V> right = null;
Entry<K,V> parent;
boolean color = BLACK;
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}接下来看一下 TreeMap 的 增加、删除、访问和迭代操作
1 增加元素
public V put(K key, V value) {
Entry<K, V> t = root;
if (t == null) {
root = new Entry<K, V>(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) {
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);
} while (t != null);
} else {
if (key == null)
throw new NullPointerException();
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);
} while (t != null);
}
Entry<K, V> e = new Entry<K, V>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}在 TreeMap 的 put() 的实现方法中主要分为两个步骤
第一，对于排序二叉树的创建，其添加节点的过程如下：
1. 以根节点为初始节点进行检索
2. 与当前节点进行比对，若新增节点值较大，则以当前节点的右子节点作为新的当前节点。否则以当前节点的左子节点作为新的当前节点
3. 循环递归2步骤知道检索出合适的叶子节点为止
4. 将新增节点与3步骤中找到的节点进行比对，如果新增节点较大，则添加为右子节点；否则添加为左子节点
5. 按照这个步骤我们就可以构建出一颗搜索二叉树
第二，优化搜索二叉树，构架一棵平衡二叉树
fixAfterInsertion 方法对搜索二叉树进行优化，优化的过程会涉及到红黑树的左旋、右旋、着色三个基本操作。（具体算法我不清楚，后续更正）
TreeMap 提供了两种对元素 key 排序方法
- 通过在构造 TreeMap 时传入指定的 Comparator 对象，调用Comparator.compare(key1，key2)方法进行比较。
- Key 必须继承 Comparable 接口，实现 compareTo 方法，调用 key1.compareTo(key2)方法进行比较。
1 TreeMap 与 HashMap 、Hashtable 不同的是，TreeMap 使用 compareTo 或者 compare 方法完成 key 的唯一性检验，而后两者通过 equals 和 hashcode 方法
下面的测试用例中，compareTo 方法与 hashcode 、equlas方法规则不同，导致 hm 容器中只有一个元素，输出结果为 1 2 3 4 5 5
public class NoName {
public static void main(String[] args) throws InterruptedException {
TreeMap<A,String> tm = new TreeMap<A,String>();
tm.put(new A(), "1");
tm.put(new A(), "2");
tm.put(new A(), "3");
tm.put(new A(), "4");
tm.put(new A(), "5");
Set<Map.Entry<A,String>> entries = tm.entrySet();
for(Map.Entry entry : entries){
System.out.println(entry.getValue());
}
HashMap<A,String> hm = new HashMap<A,String>(tm);
Set<Map.Entry<A,String>> entries_1 = hm.entrySet();
for(Map.Entry entry : entries_1){
System.out.println(entry.getValue());
}
}
private static final class A implements Comparable{
public int compareTo(Object o) {
return 1;
}
public int hashCode() {
return 0;
}
public boolean equals(Object obj) {
return true;
}
}
}2 TreeMap 没有提供同步机制
3 TreeMap 通过 Comparable 形式排序时，不允许 key = null ,因为调用 compareTo 方法会抛出异常
*4 TreeMap 通过 Comparator 形式排序时，是否允许 key = null ，取决于你指定的 Comparator 对象的 compare 方法的具体实现。
2 删除元素
public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}3 访问元素
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}4 迭代元素
TreeMap 提供了三种 Collection 视图，分别是键集、值集合键_值集，不同的是，这些集合都按照一定规则进行了排序
TreeMap 总结
- 底层由红黑树实现
- 未提供同步机制
- 加入元素时进行了排序，通过 Comparator 或者 Comparable
- 使用 Comparator 或者 Comparable 来确定 key 是否重复，不再使用 hashcode 和 equals 方法。
- 允许 value = null
- 使用 Comparable 比较方式时，不允许 key = null，但是使用 Comparator 方式时，是否允许 key = null，取决于 Comparator.compare（）方法的实现方式
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
