最近正准备回顾一下Java，所以在此做一些记录。
关于树节点的先略过，下次进行补充
先简单看一下使用的链表节点的定义
1 /** 2 * 节点 3 */ 4 static class Node<K,V> implements Map.Entry<K,V> { 5 //hash值 6 final int hash; 7 //存放的键 8 final K key; 9 //存放的值 10 V value; 11 //下一个节点 12 Node<K,V> next; 13 //构造器 14 Node(int hash, K key, V value, Node<K,V> next) { 15 this.hash = hash; 16 this.key = key; 17 this.value = value; 18 this.next = next; 19 } 20 21 public final K getKey() { return key; } 22 public final V getValue() { return value; } 23 public final String toString() { return key + "=" + value; } 24 //hashCode方法 25 public final int hashCode() { 26 return Objects.hashCode(key) ^ Objects.hashCode(value); 27 } 28 29 public final V setValue(V newValue) { 30 V oldValue = value; 31 value = newValue; 32 return oldValue; 33 } 34 //重写的equals方法 35 public final boolean equals(Object o) { 36 if (o == this) 37 return true; 38 if (o instanceof Map.Entry) { 39 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 40 if (Objects.equals(key, e.getKey()) && 41 Objects.equals(value, e.getValue())) 42 return true; 43 } 44 return false; 45 } 46 }
1.put(K key, V value) 存放一个键值对
1 /** 2 * 存放一个键值对 3 * @param key 键 4 * @param value 值 5 */ 6 public V put(K key, V value) { 7 //计算key的hash值，存放一个键值对 8 return putVal(hash(key), key, value, false, true); 9 } 10 11 /** 12 * 存放一个键值对 13 * 14 * @param hash 根据key计算出来的hash值 15 * @param key 存放的键 16 * @param value 存放的值 17 * @param onlyIfAbsent 18 * @param evict 19 */ 20 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 21 boolean evict) { 22 Node<K,V>[] tab; 23 Node<K,V> p; 24 int n, i; 25 // 将tab设置为hashmap中存放数据的数组，n设置为数组的大小 26 if ((tab = table) == null || (n = tab.length) == 0) 27 //如果数组为空或者数组大小为0，生成一个新的数组 28 n = (tab = resize()).length; 29 //i设置成数组的大小减1与上hash值 30 //因为是与操作，所以i的值一定保证在数组范围里 31 //lenth = 2n 时，X % length = X & (length - 1) 32 //大家可以去搜一下验证 33 if ((p = tab[i = (n - 1) & hash]) == null) 34 //说明这个数组当前索引位置还没有存放数据，则放置新的节点 35 tab[i] = newNode(hash, key, value, null); 36 else { 37 //数组当前索引已经有值的情况 38 //p为当前数组索引上的节点 39 Node<K,V> e; K k; 40 if (p.hash == hash && 41 ((k = p.key) == key || (key != null && key.equals(k)))) 42 //当前数组索引上的节点key等于放入的key，将e设置成p 43 e = p; 44 else if (p instanceof TreeNode) 45 //p节点已经转换成了树节点，往树节点上增加节点 46 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 47 else { 48 //还是链表节点，往后遍历链表节点 49 for (int binCount = 0; ; ++binCount) { 50 //将e设置成后一个节点 51 if ((e = p.next) == null) { 52 //如果是空节点，则将新节点挂在链表上 53 //此时e为null值 54 p.next = newNode(hash, key, value, null); 55 //如果链表的节点数大于等于8，将链表转换成树节点 56 //TREEIFY_THRESHOLD = 8 57 if (binCount >= TREEIFY_THRESHOLD - 1) 58 //转变成树节点 59 treeifyBin(tab, hash); 60 break; 61 } 62 //如果下一个key等于要存放的节点的key，退出循环 63 if (e.hash == hash && 64 ((k = e.key) == key || (key != null && key.equals(k)))) 65 break; 66 //指向下一个节点 67 p = e; 68 } 69 } 70 //e不为null，说明想要存放的节点的key重复 71 if (e != null) { 72 //获取旧值 73 V oldValue = e.value; 74 //参数onlyIfAbsent = false或旧值为空值，新值替换旧值 75 if (!onlyIfAbsent || oldValue == null) 76 e.value = value; 77 //hashmap中是个空方法 78 afterNodeAccess(e); 79 //返回旧值 80 return oldValue; 81 } 82 } 83 ++modCount; 84 //放入一个新值后判断总大小是否大于阈值 85 if (++size > threshold) 86 //扩容，也就是会生成一个新的数组 87 resize(); 88 //hashmap中是个空方法 89 afterNodeInsertion(evict); 90 return null; 91 } 92 93 /** 94 * 扩容的操作，会重新生成数组 95 * 96 * @return 新的数组 97 */ 98 final Node<K,V>[] resize() { 99 //保存旧数组 100 Node<K,V>[] oldTab = table; 101 //保存旧数组的大小，旧数组为null则大小设置0 102 int oldCap = (oldTab == null) ? 0 : oldTab.length; 103 //保存旧的阈值 104 int oldThr = threshold; 105 //定义新的数组大小和阈值变量 106 int newCap, newThr = 0; 107 //如果旧数组大小大于0 108 if (oldCap > 0) { 109 //判断旧数组大小是否大于定义的最大值 110 // MAXIMUM_CAPACITY = 1 << 30; 111 if (oldCap >= MAXIMUM_CAPACITY) { 112 //设置阈值为int的最大值 113 threshold = Integer.MAX_VALUE; 114 //返回旧数组，数组已经很大了 115 return oldTab; 116 } 117 //如果旧数组大小还没有超过最大值的话 118 //新数组的大小设置为旧数组的2倍 119 //判断新数组的大小小于最大值并且旧数组的大小大于默认值16 120 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 121 oldCap >= DEFAULT_INITIAL_CAPACITY) 122 //新的阈值扩大成2倍 123 newThr = oldThr << 1; 124 } 125 else if (oldThr > 0) 126 //一般初始化的时候设置了大小的，会计算出threshold阈值，所以第一次put会在这里 127 //如果旧阈值大于0，则设置新的数组大小为旧阈值大小 128 newCap = oldThr; 129 else { 130 //一般new的时候没有设置初始值大小的时候，第一次put操作会到这里 131 //设置新的数组大小为默认值16 132 newCap = DEFAULT_INITIAL_CAPACITY; 133 //设置新的阈值大小为默认负载因子 * 默认值 0.75*16 = 12 134 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 135 } 136 //如果新的阈值=0，只有两种情况 137 //1.else if (oldThr > 0)的时候，也就是初始化的时候指定了大小第一次存放值，阈值大于等于数组大小，会降低阈值 138 //2.(newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY 139 if (newThr == 0) { 140 //根据新的数组大小计算阈值 141 float ft = (float)newCap * loadFactor; 142 //判断新数组大小和阈值大小是否超过定义的最大值 143 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 144 (int)ft : Integer.MAX_VALUE); 145 } 146 //确定新的阈值 147 threshold = newThr; 148 @SuppressWarnings({"rawtypes","unchecked"}) 149 //创建新的数组 150 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 151 //设置新的数组 152 table = newTab; 153 //如果旧数组不为空，需要迁移所有的数组 154 if (oldTab != null) { 155 //遍历 156 for (int j = 0; j < oldCap; ++j) { 157 Node<K,V> e; 158 //设置e为当前数组索引的值 159 if ((e = oldTab[j]) != null) { 160 //清空之前的值 161 oldTab[j] = null; 162 //如果数组索引后面不存在链表或树节点 163 if (e.next == null) 164 //计算当前节点在新数组的位置并放置 165 newTab[e.hash & (newCap - 1)] = e; 166 else if (e instanceof TreeNode) 167 //如果该节点是树结构 168 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 169 else { 170 //如果是链表结构 171 Node<K,V> loHead = null, loTail = null; 172 Node<K,V> hiHead = null, hiTail = null; 173 Node<K,V> next; 174 do { 175 //保存链表下一个节点 176 next = e.next; 177 //根据判断值，将节点存放在两条链表当中 178 //通过e.hash & oldCap计算了在新数组中的索引位置 179 //e.hash & oldCap == 0 索引位置不发生变化 180 // ！=0，索引位置下移了旧数组大小 181 // 大家可以去验证一下 182 if ((e.hash & oldCap) == 0) { 183 if (loTail == null) 184 loHead = e; 185 else 186 loTail.next = e; 187 loTail = e; 188 } 189 else { 190 if (hiTail == null) 191 hiHead = e; 192 else 193 hiTail.next = e; 194 hiTail = e; 195 } 196 } while ((e = next) != null); 197 //将链表存放到新数组对应的索引位置 198 if (loTail != null) { 199 loTail.next = null; 200 newTab[j] = loHead; 201 } 202 if (hiTail != null) { 203 hiTail.next = null; 204 newTab[j + oldCap] = hiHead; 205 } 206 } 207 } 208 } 209 } 210 return newTab; 211 }
2.get(Object key) 根据键获取值
1 /** 2 * 根据键获取值 3 * @param key 键 4 * @return 对应的值 5 */ 6 public V get(Object key) { 7 Node<K,V> e; 8 //调用了getNode方法获取节点，再获取值 9 return (e = getNode(hash(key), key)) == null ? null : e.value; 10 } 11 12 /** 13 * 根据hash和key获取值 14 * 15 * @param hash hash值 16 * @param key 键 17 * @return 返回对于的节点 18 */ 19 final Node<K,V> getNode(int hash, Object key) { 20 Node<K,V>[] tab; Node<K,V> first, e; int n; K k; 21 //存在数组并且数组大小大于0并且根据hash计算的数组索引上存在节点，否则返回null 22 if ((tab = table) != null && (n = tab.length) > 0 && 23 (first = tab[(n - 1) & hash]) != null) { 24 //first为数组对应索引上的第一个节点，如果对应的hash和key都相等，则返回 25 if (first.hash == hash && 26 ((k = first.key) == key || (key != null && key.equals(k)))) 27 return first; 28 //first的下一个节点不为空 29 if ((e = first.next) != null) { 30 //树结构的情况 31 if (first instanceof TreeNode) 32 return ((TreeNode<K,V>)first).getTreeNode(hash, key); 33 //链表的情况 34 do { 35 //遍历计算，获取对应的key的节点 36 if (e.hash == hash && 37 ((k = e.key) == key || (key != null && key.equals(k)))) 38 return e; 39 } while ((e = e.next) != null); 40 } 41 } 42 return null; 43 }
3.containsKey(Object key) 是否存在对应的key
1 /** 2 * 是否存在对应的key 3 * 4 * @param key 键 5 * @return true、false 6 */ 7 public boolean containsKey(Object key) { 8 //判断getNode方法是否获取到值 9 return getNode(hash(key), key) != null; 10 } 11 12 /** 13 * 根据hash和key获取值 14 * 15 * @param hash hash值 16 * @param key 键 17 * @return 返回对于的节点 18 */ 19 final Node<K,V> getNode(int hash, Object key) { 20 Node<K,V>[] tab; Node<K,V> first, e; int n; K k; 21 //存在数组并且数组大小大于0并且根据hash计算的数组索引上存在节点，否则返回null 22 if ((tab = table) != null && (n = tab.length) > 0 && 23 (first = tab[(n - 1) & hash]) != null) { 24 //first为数组对应索引上的第一个节点，如果对应的hash和key都相等，则返回 25 if (first.hash == hash && 26 ((k = first.key) == key || (key != null && key.equals(k)))) 27 return first; 28 //first的下一个节点不为空 29 if ((e = first.next) != null) { 30 //树结构的情况 31 if (first instanceof TreeNode) 32 return ((TreeNode<K,V>)first).getTreeNode(hash, key); 33 //链表的情况 34 do { 35 //遍历计算，获取对应的key的节点 36 if (e.hash == hash && 37 ((k = e.key) == key || (key != null && key.equals(k)))) 38 return e; 39 } while ((e = e.next) != null); 40 } 41 } 42 return null; 43 }
4.remove(Object key) 删除对应的key
1 /** 2 * 删除对应的key 3 * 4 * @param 键 5 * @return 对应的值 6 */ 7 public V remove(Object key) { 8 Node<K,V> e; 9 //调用removeNode方法 10 return (e = removeNode(hash(key), key, null, false, true)) == null ? 11 null : e.value; 12 } 13 14 /** 15 * 删除对应的节点 16 * 17 * @param hash hash值 18 * @param key 键 19 * @param value 值 20 * @param matchValue 是否开启value值的匹配 21 * @param movable 22 * @return 返回对应的节点 23 */ 24 final Node<K,V> removeNode(int hash, Object key, Object value, 25 boolean matchValue, boolean movable) { 26 Node<K,V>[] tab; Node<K,V> p; int n, index; 27 //判断数组不为空并且数组大小大于0并且根据hash值计算的数组索引所在的节点不为空 28 if ((tab = table) != null && (n = tab.length) > 0 && 29 (p = tab[index = (n - 1) & hash]) != null) { 30 Node<K,V> node = null, e; K k; V v; 31 //hash所在的数组索引位置的节点等于寻找的key 32 if (p.hash == hash && 33 ((k = p.key) == key || (key != null && key.equals(k)))) 34 node = p; 35 //寻找下一个节点 36 else if ((e = p.next) != null) { 37 //树结构的查询 38 if (p instanceof TreeNode) 39 node = ((TreeNode<K,V>)p).getTreeNode(hash, key); 40 else { 41 //链表结构的查询 42 do { 43 //遍历获取到对应key的节点 44 if (e.hash == hash && 45 ((k = e.key) == key || 46 (key != null && key.equals(k)))) { 47 node = e; 48 break; 49 } 50 p = e; 51 } while ((e = e.next) != null); 52 } 53 } 54 //根据key查询到节点 55 //matchValue 是否开始value值的匹配 56 //开启value值的匹配徐娅萍判断value值是否相等 57 if (node != null && (!matchValue || (v = node.value) == value || 58 (value != null && value.equals(v)))) { 59 //节点在树结构中 60 if (node instanceof TreeNode) 61 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); 62 //节点在数组索引的上 63 else if (node == p) 64 //数组索引指向节点的下一个 65 tab[index] = node.next; 66 //在链表中 67 // p为找到节点的上一个节点，将p的下一个节点指向找到节点的下一个节点 68 else 69 p.next = node.next; 70 ++modCount; 71 //数量减1 72 --size; 73 //hashmap中为空方法 74 afterNodeRemoval(node); 75 return node; 76 } 77 } 78 //返回null 79 return null; 80 }
5.containsValue(Object value) 是否存在对应的值
1 /** 2 * 是否存在对应的值 3 * 4 * @param value 需要查询的值 5 */ 6 public boolean containsValue(Object value) { 7 Node<K,V>[] tab; V v; 8 //数组不为空并且数组大于0 9 if ((tab = table) != null && size > 0) { 10 //遍历数组 11 for (int i = 0; i < tab.length; ++i) { 12 //数组索引中的节点不为空，继续遍历 13 for (Node<K,V> e = tab[i]; e != null; e = e.next) { 14 //如果存在相等的值 15 if ((v = e.value) == value || 16 (value != null && value.equals(v))) 17 //返回true 18 return true; 19 } 20 } 21 } 22 //返回false 23 return false; 24 }