HashMap、HashTable源码分析

java.util

 

接口 Map<K,V>

 

类型参数：

 

K - 此映射所维护的键的类型

 

V - 映射值的类型

 

所有已知子接口：

 

Bindings, ConcurrentMap<K,V>, ConcurrentNavigableMap<K,V>, LogicalMessageContext, MessageContext, NavigableMap<K,V>, SOAPMessageContext, SortedMap<K,V>

 

所有已知实现类：

 

AbstractMap, Attributes, AuthProvider, ConcurrentHashMap, ConcurrentSkipListMap, EnumMap, HashMap, Hashtable, IdentityHashMap, LinkedHashMap, PrinterStateReasons, Properties, Provider, RenderingHints, SimpleBindings, TabularDataSupport, TreeMap, UIDefaults, WeakHashMap

主要分析一下：HashMap, TreeMap, Hashtable, SortedMap, ConcurrentHashMap

 

	HashMap	HashTable
数据结构	Entry<?,?>[] table Size	Entry<K,V>[] table count
初始值	初始容量默认 16，加载因子是 0.75	初始容量默认 11，加载因子是 0.75
是否有序	无序	无序
安全性	不安全	安全
扩容机制	当前容量的两倍扩容	当前容量的两倍+1扩容
性能分析	插入慢，查询、删除速度一样（计算获得index，遍历table）	rehash时性能慢，插入慢，查询、删除速度一样（计算获得index，遍历table）

容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。

 加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。

 当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。

 

1，HashMap    基于哈希表的 Map 接口的实现。

Put()：添加方法

 

• 1，初始化哈希表

• 2，计算hash值

• 3，rehash容量2倍扩容

 

• 4，计算索引

 

 

hash表的数据结构为：链表式数组。

 

Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

 

Entry<K,V>	说明
K key	key
V value	value
int hash	key的hash值
Entry<K,V> next	Next Entry

索引冲突处理方式为将新值放在第一位，并将next指向旧值.

 

Get():查询方法

计算Key的Hash值遍历获取当前key的value

 

Remove():删除方法

 

使用建议：

• 创建线程安全的HashMap方式如下：

Map m = Collections.synchronizedMap(new HashMap(...));

• 指定map大小

在知道map大小情况下，建议在创建时指定map大小    

• 遍历方式

使用for循环遍历，效率高于Iterator

 

2，HashTable

 

Put()：添加方法

 

• Rehash容量2倍+1 扩容

 

3，TreeMap

 

基于红黑树（Red-Black tree）的 NavigableMap实现。该映射根据其键的自然顺序进行排序。

 

Put():添加方法

 

//修复红黑树

 

  /** From CLR */

 

    private void fixAfterInsertion(Entry<K,V> x) {

 

        x.color = RED;

 

 

 

        while (x != null && x != root && x.parent.color == RED) {

 

            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {

 

                Entry<K,V> y = rightOf(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 == 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;

 

    }