mojinhui33
0%

HashMap

发表于 更新于 分类于

Map

2-3树/红黑树

因为2-3树为了保持平衡性，维护的时候需要大量的节点交换，于是有了再2-3树的理论基础上发明了红黑树

红黑树是对2-3查找树的改进，它能用统一的方式完成所有变换

红黑树是一种平衡二叉树，因此没有3-节点

红黑树基本介绍

红黑树进阶

红黑树原理与实现

简单常用的Map功能

  1. 添加功能

    V put (K key, V value):添加元素

     如果键是第一次存储，就直接存储元素，返回null

 如果不是第一次存在，就用值把以前的值替换掉，返回以前的值

  2. 删除功能

    void clear():移除所有的键值对元素

    V remove(Object key):根据键删除值，并把值返回

  3. 判断功能

    boolean containsKey(Object key):判断集合是否包含指定的键

    boolean containsValue(Object value):判断集合是否包含指定的值

    boolean isEmpty():判断集合是否为空

  4. 获取功能

    Set<Map.Entry<K Key, V value> entrySet():返回的是键值对对象的集合

    V get(Object key):根据键获取值

    Set keySet():获取集合中所有的键的集合

    Collection values():获取集合中所有值的集合

  5. 长度功能

    int size():返回集合中键值对的对数

HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//初始容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量，2的31次方
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认装载因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//当添加一个元素被添加到至少有TREEIFY_THRESHOLD个节点的桶中，桶中链表将被转化为树形结构
static final int TREEIFY_THRESHOLD = 8;
//同上，不过是将树形结构转为链表
static final int UNTREEIFY_THRESHOLD = 6;
//桶可能被转化为树形结构的最小容量
static final int MIN_TREEIFY_CAPACITY = 64;
//该表在首次使用时初始化，并根据需要调整大小。分配时，长度始终是2的幂。（我们在某些操作中也允许长度为零，以允许*当前不需要的引导机制。
transient Node<K,V>[] table;

构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//初始容量，装载因子
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);
        this.loadFactor = loadFactor;
    //返回一个大于输入参数且最近的2的整数次幂的数
        this.threshold = tableSizeFor(initialCapacity);
    }
后面几个构造方法都差不多

put

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

//得到key的哈希值，并与其高16位做异或运算，与下面的方法一起减少了碰撞冲突的可能性
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
    //当散列表为null时，调用resize()初始化散列表
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
    //表的默认初始容量是16，放到散列表中就是0-15的位置，所以需要减1.可以发现：再做与运算的时候，仅仅是后四位有效（因为n-1二进制最大位就是第四位），那么如果我们key的哈希值高位变化很大，地位变化很小。直接拿过去不经过异或运算，这就会导致计算出来的Hash值相同概率增加
    //没有发生碰撞，直接添加元素到散列表中
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
    //发生了碰撞
        else {
            Node<K,V> e; K k;
        //要插入的元素，桶的hash和key都相等，记录下来
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
        //如果是红黑树结构，就调用树的插入方法
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
        //链表结构，找到了key印社的节点，就记录这个节点，推出循环，如果没有找到，就在链表尾部插入这个节点。
        //插入后如果发现临界值大于TREEIFY_THRESHOLD，转成红黑树
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    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;
    }

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 &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
    //如果旧容量<=0,而且旧阈值>0，数组的新容量设置为老数组扩容的阈值
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
    //第一次初始化散列表
        else {               // zero initial threshold signifies using defaults
            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) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    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;
                        }
                    }
                }
            }
        }
        return newTab;
    }

get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //如果这个表不为空 且 表的长度大于0 且 计算出来的值是在哈希表上
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
        //如果第一个值就匹配，返回第一个值
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
        //如果这个值仅仅是hash值匹配，判断是否是树
            if ((e = first.next) != null) {
            //查找红黑树或者遍历链表来查询
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

remove

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
@Override
    public boolean remove(Object key, Object value) {
        return removeNode(hash(key), key, value, true, true) != null;
    }

final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
    //表不为空 且 长度大于0 且 当前hash位置的值不为空
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
        //如果刚好匹配成功
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
        //否则查看是否是树或链表
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
        //如果找到了，分三种情况
        //是红黑树，是链表，在桶的首位
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

HashMap与Hashtable

存储结构和实现来讲基本都相同。

最大的不同Hashtable是线程安全的

不允许key和value为null

它是一个过时的集合类，不建议在新代码中使用，一般用ConcurrentHashMap替换