Java集合框架-----Map源码学习
发布日期:2021-06-28 20:09:15
浏览次数:2
分类:技术文章
本文共 10210 字,大约阅读时间需要 34 分钟。
参考:
https://www.cnblogs.com/skywang12345/p/3310835.html https://blog.csdn.net/u010890358/article/details/80496144 https://joonwhee.blog.csdn.net/article/details/78996181 https://www.cnblogs.com/leesf456/p/5242233.html https://blog.csdn.net/AJ1101/article/details/79413939基本特性: 是一个散列表,它存储的内容是键值对(key-value)映射。线程不安全,无序,允许null键和null值
散列表:参考:http://data.biancheng.net/view/107.html 散列表:(速度快,空间大,无序,可能有冲突)又叫哈希表(Hash Table),是能够通过给定的关键字的值直接访问到具体对应的值的一个数据结构。 也就是说,把关键字映射到一个表中的位置来直接访问记录,以加快访问速度。HashMap 的实例有两个参数影响其性能:“初始容量”(默认初始容量16) 和 “加载因子”(默认加载因子是 0.75)。
加载因子: 当前有效数据大于 加载因子与当前容量的乘积时, hash会扩容源码学习(基于1.8)
HashMap的主要成员变量 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // (16)默认的table初始容量 static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量 static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认的负载因子 static final int TREEIFY_THRESHOLD = 8; //链表长度大于该参数转红黑树 static final int UNTREEIFY_THRESHOLD = 6; //当树的节点数小于等于该参数转成链表 static final int MIN_TREEIFY_CAPACITY = 64; //调整树化的一个阈值 transient Node<K,V>[] table: //这是一个Node类型的数组 int threshold; // 阈值 表示当前HashMap能够承受的最多的键值对数量,一旦超过这个数量HashMap就会进行扩容 final float loadFactor; //负载因子,用于扩容 transient int modCount:表示当前HashMap修改次数HashMap的构造方法:
// 默认构造函数。 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } // 指定“容量大小”的构造函数 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } // 指定“容量大小”和“加载因子”的构造函数 public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) //容量小于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; this.threshold = tableSizeFor(initialCapacity); } // 包含“子Map”的构造函数 public HashMap(Map m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }
常用方法源码:
1, V put(K key, V value) put源码比较多,只能分开来 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } //获取hash static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } //插入 这个太长了 putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)最后慢慢讲 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { ...}
2, V get(Object key) public V get(Object key) { Nodee; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node getNode(int hash, Object key) { Node [] tab; Node first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { //map中键值对不为空的情况 hash可以直接确定值在数组的位置 if (first.hash == hash && // always check first node // 判断数组上的值是不是 hash相等 K相等 ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) // 如果这个节点挂的是树,就getTreeNode(hash, key) return ((TreeNode )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; } final TreeNode getTreeNode(int h, Object k) { return ((parent != null) ? root() : this).find(h, k, null); } final TreeNode root() { for (TreeNode r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } } //在红黑树上查找 final TreeNode find(int h, Object k, Class kc) { TreeNode p = this; do { int ph, dir; K pk; TreeNode pl = p.left, pr = p.right, q; if ((ph = p.hash) > h) p = pl; else if (ph < h) p = pr; else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p; else if (pl == null) p = pr; else if (pr == null) p = pl; else if ((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0) p = (dir < 0) ? pl : pr; else if ((q = pr.find(h, k, kc)) != null) return q; else p = pl; } while (p != null); return null; }
3, V remove(Object key) public V remove(Object key) { Nodee; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } //移除节点 final Node removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node [] tab; Node p; int n, index; if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node 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 )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 )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; }
4, boolean containsKey(Object key) //就是调用get方法 public boolean containsKey(Object key) { return getNode(hash(key), key) != null; }5, boolean containsValue(Object value) //遍历大法好 public boolean containsValue(Object value) { Node[] tab; V v; if ((tab = table) != null && size > 0) { for (int i = 0; i < tab.length; ++i) { for (Node e = tab[i]; e != null; e = e.next) { if ((v = e.value) == value || (value != null && value.equals(v))) return true; } } } return false; }
```bash6, Collectionvalues() public Collection values() { Collection vs = values; if (vs == null) { vs = new Values(); values = vs; } return vs; } //组装成新的对象 final class Values extends AbstractCollection { public final int size() { return size; } public final void clear() { HashMap.this.clear(); } public final Iterator iterator() { return new ValueIterator(); } public final boolean contains(Object o) { return containsValue(o); } public final Spliterator spliterator() { return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0); } public final void forEach(Consumer action) { Node [] tab; if (action == null) throw new NullPointerException(); if (size > 0 && (tab = table) != null) { int mc = modCount; for (int i = 0; i < tab.length; ++i) { for (Node e = tab[i]; e != null; e = e.next) action.accept(e.value); } if (modCount != mc) throw new ConcurrentModificationException(); } } } 最重要的put方法: 正常插入 返回null 覆盖插入 返回被覆盖的值 public V put(K key, V value) {return putVal(hash(key)①, key, value, false, true); } ①hash方法:hash(key) static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); /** * key.hashCode() 取key的hashCode,使用改的是Object方法 * h >>> 16 hash值无符号右移16位(正数显示不出来,只有负数才有区别) * hash(key) 定位桶的位置是利用元素的key的哈希值对数组长度取模得到 **/ }
putVal() 方法 参考: https://blog.csdn.net/AJ1101/article/details/79413939putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; //table 为空 tab.length 长度为空 必要参数初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //确定桶的位置的索引 tab[i = (n - 1) & hash] //如果此处索引位置为空, 则新建一个 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { 如果Hash冲突 Node 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 )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); // 链表长度大于8时,将链表转红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //如果hash依然冲突,且相等,直接退出循环 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;}
具体的这个还是看: https://blog.csdn.net/AJ1101/article/details/79413939
我是面向面试学这个的,所以直接看这个面试的问题吧? https://www.cnblogs.com/zengcongcong/p/11295349.html https://www.cnblogs.com/tianzhihensu/p/11972780.html1,HashMap在多线程环境中什么时候会出现问题?
https://www.cnblogs.com/developer_chan/p/10450908.html JDK1.7中,多线程造成的问题 扩容时会造成环形链或数据丢失 , JDK1.8 https://blog.csdn.net/fumitzuki/article/details/82760236 https://blog.csdn.net/qq_36520235/article/details/82417949 ①,数据丢失, ②,size()的值不准确2,为什么引入红黑树?
红黑树的引入保证了在大量hash冲突的情况下,HashMap还具有良好的查询性能 为什么桶的数量超过8才转化为红黑树,小于8是,链表和红黑树的复杂度查不到,其他相关参考:
https://blog.csdn.net/shenhaiwen/article/details/79001039 https://zhuanlan.zhihu.com/p/76735726 https://www.cnblogs.com/wang-meng/p/9b6c35c4b2ef7e5b398db9211733292d.html转载地址:https://blog.csdn.net/xy3233/article/details/110355578 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年04月19日 16时46分00秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Java开发必用的工具包
2019-04-29
世界500强公司要求员工必须熟练掌握的七种工作方法
2019-04-29
九个做事的顺序,你会更加优秀
2019-04-29
史上最详细的Hadoop环境搭建
2019-04-29
最近经历的一些大数据(Spark/Hadoop)面试题
2019-04-29
Hadoop MapReduce原理及实例
2019-04-29
Java 集合系列目录(Category)
2019-04-29
redis永久设置或取消密码
2019-04-29
Git .gitignore配置学习
2019-04-29
git remote 删除添加的远程地址
2019-04-29
LeetCode 338. 比特位计数
2019-04-29
LeetCode 190. 颠倒二进制位
2019-04-29
LeetCode 268. 丢失的数字
2019-04-29
LeetCode 231. 2 的幂
2019-04-29
LeetCode 191. 位1的个数
2019-04-29
LeetCode 476. 数字的补数
2019-04-29
LeetCode 342. 4的幂
2019-04-29
El表达式
2019-04-29
springboot banner打印,控制台springboot图案怎么来的
2019-04-29
linux shell內建命令区分--type
2019-04-29