- 1使用 React 和 Tailwind CSS 创建漂亮 Hero Section
- 25.28.
- 3C++ 回文制造机：给定字符串形成最短回文串_c语言给字符串补上最少的字符使其变成回文字符串
- 4最新官方权威带有审图号的中国行政区划数据来了！ 审图号:GS(2024)0650号_中国行政区数据 gdb
- 5OpenCV 并行计算函数 parallel_for_ 的使用
- 6【数据分析入门】人工智能、数据分析和深度学习是什么关系？如何快速入门 Python Pandas？_深度学习和数据分析有什么区别
- 77-11 树的遍历（25 分）
- 8学习通判作业的快捷方法(with Python,vimium C)_学习通判作业快
- 9MySQL面经
- 10java spark读写hdfs文件_Spark读取HDFS中的Zip文件
HashMap总结以及顺序表、链表、哈希表、数据结构_哈希表和顺序表区别
赞
踩
HashMap总结以及顺序表、链表、哈希表、数据结构
首先本文是在下浅显的自我理解，欢迎各位大佬喷我。
要挖底层，必须先瞄一眼数据结构
- 1
数据结构
在数据结构中，有俩个存储数据方式为顺序表和链表。
顺序表：顾名思义，就是存储区间是连续的，大概是下图的样子
如图所示，在内存中，顺序表是连续的，这里以int类型数组为例，因为数组是典型的顺序表，因为顺序表存储单元是连续的，优势也就出来了，查找很快，知道地址以后直接访问，比如想要去取arr数组中的第五个元素，直接用arr[4]就可以取到其内容;也正是如此，上帝给你打开一扇窗户的就是就会随手关上一扇门，所以顺序表的插入和删除这俩扇门就被关上了，不是说关一扇门么，为啥关俩个，上帝乐意呀。
画风一转，来个插入删除哈哈：
顺序表插入：顺序表的插入，前提是，插入的位置，在顺序表的定义范围之内，比如说定义了8个长度数组 int[] arr = new int[8];你非要插入arr[11] ,直接就OOB了，当然也要从0开始，别整有的没的从负数干,在0~arr.length-1直接插入都没有问题，在最后一个元素插入就相当于直接把arr[arr.length]给赋值了，直接覆盖，之前数字就没了，从其他位置插入的方法就是，需要先把插入位置及之后的元素向后移动一下，然后空出来当前位置，再进行插入，当然这个方法得自己实现，也有utils帮你干了，但是，顺序表，这么干的意义不大。下面是简单的图像描述：
因为每插入一个，就要将插入位置以及之后的向后移动一个位置，所以，插入的难度非常高。
顺序表删除：
删除的流程与上面叙述的插入方式刚好是逆向的一个过程，需要找到需要删除的位置，从删除位置后面的一个开始，依次向前覆盖一个单位，直到完全覆盖结束。
顺序表扩容：
顺序表是不能在原顺序表上进行扩容的，因为起初开辟空间的时候，就已经设置了顺序表的长度，不能进行后期扩容，比如现在的位置是0x0001-0x0010，想要在0x0011位置继续扩容到当前位置，是不允许的，因为之前已经定义的0x0001-0x0010你使用未释放的时候，之后的空间是不被占用的，可能0x0011已经被使用的，或者没有被使用是无法确定的，无法确定的东西，使用了可能会出错，不使用一定不会造成数据错误，所以这里不进行使用，如果顺序表需要扩容，需要找新的大的空间，将现在的内容copy过去，然后释放旧的，使用新的数组就可以。
//Java举例
//原数组
int[3] arrOld = new int[3];
int[] arrNew=new int[arrOld .length*2] //新数组长度为原数组2倍
for(int i=0;i<arrOld .length;i++){ //复制
arrNew[i]=arrOld [i];
}
arrOld = null;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
链表：链条知道吧
嗯，就这玩意，链表就是大概这个内容的，由一个一个数据单元连接起来的东西，组成一个存储的区间。
链表的存储区间比较离散，在内存中，可能逻辑上是链条，实际上，是通过每个数据单元的地址进行按址寻值的，先上个图：
假设现在有一个列表，内容为{“我”,”爱”,”你”,”祖国”}
以java中的list抽象一下举个例子更好的举例当然是C语言的结构体，就是：
这样的，
list.get(0)–>我
list.get(1)–>爱
list.get(2)–>你
list.get(3)–>祖国
在内存中，大概抽象一下是这样的：
嗯，图是这样的，很丑，我们把我们的信息拿出来看看：
也漂亮不到哪里去，再稍微调整一下下：
哎，这次舒服多了，数据链表，用内存讲，底层实现还是C语言比较好理解，加入指针的概念，结合一个结构体，跟舒服深刻的能理解指针域和数据域的区别，数据单元也就是C中的结构体，结构是【指针域|数据域|指针域】，第一个指针域存的是当前数据域在内存中的地址，数据域就是存入的内容，第三个指针域是存的下一个数据单元的地址，也就是下一个数据单元的第一个指针域的地址，当前这里图中提到了一个head，头节点，只存了list，链表名和首个数据节点的地址，这个head头结点在C语言中实现是存在的，如果了解C就会明白，当然java也可以，如下：
主要是要注意这个Node节点，我们看一下他的实现：
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
一个LinkedList的内部类，有三个字段，第一个是泛型的数据域，我们提到的，第二个是下一个数据节点的索引next,第三个是上一个数据节点的索引，哎你也许要问当前的数据节点地址呢，java是面向对象的，对象就是当前节点的引用，所以java中的Node对比C语言中刚刚提到的结构可能就是【指针域|上一个数据节点指针域|数据域|下一个数据节点的指针域】这时候就会觉得woc刚刚不是说的三个吗，怎么突然变四个了，凭空生娃？？？，接下来，就要提到一个双向链表，既然有双向列表，那么单项链表肯定是存在的，没错上边讲解的就是单项链表，因为java中的linkedList是双向链表实现的，所以，我再来将上面的例子改成双向链表的图，就一目了然了。
就是可以根据每个节点都能找到它的前后节点在哪里，而单项列表只能找到他的下一个节点在哪里，这个会影响的数据存储的插入和删除。
说了这么多，对于数据链表，其实总结一下就是，存储是灵活的，离散的，占用内存是宽松的，接下来对比一下顺序表的讲解，对列表进行查找、插入、删除以及扩容：
链表的查询：
链表的查询，用过java中的LinkedList就知道，麻烦，死板，遍历查找，可能你用的时候是用了contains方法，来我们看看这个方法的实现：
/**
* Returns {@code true} if this list contains the specified element.
* More formally, returns {@code true} if and only if this list contains
* at least one element {@code e} such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this list is to be tested
* @return {@code true} if this list contains the specified element
*/
public boolean contains(Object o) {
return indexOf(o) != -1;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
这里调用了方法indexOf();我们再看看indexOf():
/** * Returns the index of the first occurrence of the specified element * in this list, or -1 if this list does not contain the element. * More formally, returns the lowest index {@code i} such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, * or -1 if there is no such index. * * @param o element to search for * @return the index of the first occurrence of the specified element in * this list, or -1 if this list does not contain the element */ public int indexOf(Object o) { int index = 0; if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; }
- 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
进来先判断要查找的元素是不是null，如果是null就单独查找数据为null值node节点返回他的索引index，因为下面要用到Object的equals()方法，不区分null会空指针异常，所以分开判断，因此，这里就知道了链表的数据内容是可以为null的，接下来的else里面就是进行对数据链表从前往后的一个遍历，指到找到我们要找的元素为止，相对于顺序表，这个链表的劣势就体现出来了，查询满，基本上如果查询的元素在第一个，循环一次就查到了，如果在最后一个或者不存在，就都要遍历链表长度的所有元素，时间复杂度为O(n)。
链表的插入：
对比刚刚讲过的顺序表，链表的插入就简单多了，第一链表不是顺序的存储空间，也就不存在依次往后挪动的情况，只需要在想要插入的地方，替换相近俩个数据节点的上一个数据的地址和下一个数据的地址，就可以了。通过下图，做一个简单的描述：
要插入的节点在下面，需要将上面的“哈”的下一个节点索引0x0005放到新节点“撒”的下一节点中，将“开”的上一个节点放入到新节点“撒”的上一节点索引中，然后将“撒”的索引分别放入第一个节点的下一节点索引中和第二个节点的上一个节点中，过程如图：
然后将数据放入之后结果如图：
连线以后效果:
总结：链表的插入，很灵活，只影响俩个节点的信息变动，而顺序表的插入，会影响当前数据节点之后的所有数据，相比之下，链表更加灵活。
链表的删除：
删除我们就把刚刚插入的东西删除掉，就是一个插入过程的逆过程，如图：
1：将删除节点的上一元素索引放入到下一元素的上一元素索引中；
2：将删除节点的下一元素索引放入到上一元素的下一元素索引中；
放入索引后如图：
连线以后如图：
总结：链表的插入和删除，还是相对灵活一些的，只影响前后俩个节点，时间复杂度相对顺序表有何明显下降，但是查询的实际复杂度，缺显得不尽人意了。
链表的扩容：
链表定义时没有长度限制，只要内存足够，可以一直加下去。
链表的特点我们就知道了：寻址困难，增删容易；
而顺序表的特点是：寻址容易，增删困难；
这个时候问题就出现了，为什么我们不能把顺序表的优点和顺序表的优点结合起来，取其精华、去其糟粕，然后哈希表就诞生了。
Hash Table 哈希表又叫散列表
java中的HashMap的底层实现就是哈希表，话不多说，先上个图：
图片来源百度
很明显可以看到，左边一列是熟悉的顺序表，右边是熟悉的链表，哈希表保留了顺序表的寻址容易，也保留了链表的增删方便，接下来详细说一下他的运作流程：
1.哈希表：
首先第一列是哈希表的长度，长度为16，此处可以理解为是当前哈希表的一个数组，存入了从0 - 15共16个下标，如果如接下来要存入一个数据单元内容为“hello”，他的hash值为184，然后存储时会通过hash(key)%len公司获得他的存储位置，比如当前单元的存储位置为184%16=8，那么当前元素的存储位置下标索引为8.如果当前内容的hash值为108，它的存储位置为108%16=12，他的存储位置下标索引为12；接下来在存入一个“world”，hash值为28，他的存储位置下标为28%16=12，就会将当前“world”节点插入到下标为8的节点上，然后将刚刚的“hello”节点链在“world”节点后面，进行存入。对比顺序表和链表举个例子，哈希表就是链表顺序表，举个例子就是list数组，用伪代码表示一下就是：
链表 list;
List[16] hashTable;
哈希表就可以理解为是一个长度为16的链表类型的数组，在这个数组当中，每个元素存储的内容就是一条链表的第一个头结点。
2.Java中的HashMap实现：
Java中的hashmap的底层就是哈希表的底层实现，没有码的东西总是感觉恶心，我们来点有码的东西：
HashMap的构造函数
一共有四个：
第一个HashMap(int,float) int为刚刚提到的数组长度，默认为16，可以构造时设置，float是加载因子，在HashMap容量不足时进行扩容的参数，此处可以进行设置加载因子，默认是0.75
/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ 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; this.threshold = tableSizeFor(initialCapacity); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
第二个HashMap(int),只设置初始容量，加载因子使用默认加载因子0.75
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
第三个HashMap()空参构造函数，默认容量为16，默认加载因子为0.75
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
第四个构造方法
HashMap(Map<? extends K, ? extends V> m)，是用一个旧的map，创造一个一模一样的map，但是加载因子和默认容量是16和0.75
/** * Constructs a new <tt>HashMap</tt> with the same mappings as the * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with * default load factor (0.75) and an initial capacity sufficient to * hold the mappings in the specified <tt>Map</tt>. * * @param m the map whose mappings are to be placed in this map * @throws NullPointerException if the specified map is null */ public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } /** * Implements Map.putAll and Map constructor * * @param m the map * @param evict false when initially constructing this map, else * true (relayed to method afterNodeInsertion). */ final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); if (s > 0) { if (table == null) { // pre-size float ft = ((float)s / loadFactor) + 1.0F; int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); if (t > threshold) threshold = tableSizeFor(t); } else if (s > threshold) resize(); for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } }
- 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
3.HashMap的节点：
Entry<K,V>实现类Node<K,V>
hash:当前node哈希值
key:当前的键
value:当前的值
next:下一节点的索引
node对象：当前节点索引
由此可见，HashMap中的链表是linkedList链表，每次实例化HashMap都会构造一个table数组，table数组的元素为Entry节点Node静态内部类是HashMap非常重要的一个基础bean,所以此时说HashMap是一个Entry[]数组，就更容易了理解了。
下面为HashMap的方法，此处本人直接写了一遍实在是不堪入目，就直接引用大佬原文了：
作者：AllenBolg
来源：CSDN
原文：https://blog.csdn.net/AJ1101/article/details/79413939
- 1
- 2
- 3
- 4
HashMap的putVal()
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 如果存储元素的table为空，则进行必要字段的初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 获取长度（16） // 如果根据hash值获取的结点为空，则新建一个结点 if ((p = tab[i = (n - 1) & hash]) == null) // 此处 & 代替了 % （除法散列法进行散列） tab[i] = newNode(hash, key, value, null); // 这里的p结点是根据hash值算出来对应在数组中的元素 else { Node<K,V> e; K k; // 如果新插入的结点和table中p结点的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 { 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; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; // 及时更新p p = e; } } // 如果存在这个映射就覆盖 if (e != null) { // existing mapping for key V oldValue = e.value; // 判断是否允许覆盖，并且value是否为空 if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); // 回调以允许LinkedHashMap后置操作 return oldValue; } } ++modCount; // 更改操作次数 if (++size > threshold) // 大于临界值 // 将数组大小设置为原来的2倍，并将原先的数组中的元素放到新数组中 // 因为有链表，红黑树之类，因此还要调整他们 resize(); // 回调以允许LinkedHashMap后置操作 afterNodeInsertion(evict); return null; }
- 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
HashMap的resize()
//初始化或者扩容之后元素调整 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) { // 如果原table不为空 // 如果数组长度达到最大值，则修改临界值为Integer.MAX_VALUE if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 下面就是扩容操作（2倍） else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // threshold也变为二倍 newThr = oldThr << 1; } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // threshold为0，则使用默认值 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { // 如果临界值还为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; }
- 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
HashMap的putTreeVal（）
// 红黑树插入 final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) { Class<?> kc = null; boolean searched = false; TreeNode<K,V> root = (parent != null) ? root() : this; // 找Root for (TreeNode<K,V> p = root;;) { int dir, ph; K pk; if ((ph = p.hash) > h) // 红黑树中根据hash值、key值找结点 dir = -1; else if (ph < h) dir = 1; else if ((pk = p.key) == k || (k != null && k.equals(pk))) // 找到则返回此节点 return p; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) { if (!searched) { TreeNode<K,V> q, ch; searched = true; if (((ch = p.left) != null && (q = ch.find(h, k, kc)) != null) || ((ch = p.right) != null && (q = ch.find(h, k, kc)) != null)) return q; } dir = tieBreakOrder(k, pk); } TreeNode<K,V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { // 没找到时 Node<K,V> xpn = xp.next; TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); // 创建一个结点 if (dir <= 0) // 比较 xp.left = x; else xp.right = x; xp.next = x; // 插入 x.parent = x.prev = xp; if (xpn != null) ((TreeNode<K,V>)xpn).prev = x; moveRootToFront(tab, balanceInsertion(root, x)); // 调整 return null; } } }
- 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
HashMap的treeifyBin（）
// 链表转双向链表操作 final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; // 如果元素总个数小于64，则继续进行扩容，结点指向调节 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); // 先找到那个链表的头 else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; do { //创建红黑树根结点 TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) // 此处才是真正的转为红黑树 hd.treeify(tab); } }
- 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
HashMap的treeify()
//将链表中每个值进行红黑树插入操作 final void treeify(Node<K,V>[] tab) { TreeNode<K,V> root = null; // TreeNode<K,V> x = this 相当于初始化了一个结点 for (TreeNode<K,V> x = this, next; x != null; x = next) { next = (TreeNode<K,V>)x.next; // 初始化Root x.left = x.right = null; if (root == null) { x.parent = null; x.red = false; root = x; } else { K k = x.key; int h = x.hash; Class<?> kc = null; for (TreeNode<K,V> p = root;;) { int dir, ph; K pk = p.key; if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; else if ((kc == null && // comparableClassFor(k) 返回 k 类型的比较器 (kc = comparableClassFor(k)) == null) || // compareComparables(kc, k, pk) 返回p,pk比较的结果 (dir = compareComparables(kc, k, pk)) == 0) // tieBreakOrder(k, pk) 比较两个hash码 dir = tieBreakOrder(k, pk); // 此处进行红黑树操作 TreeNode<K,V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x; // 平衡调节 root = balanceInsertion(root, x); break; } } } } // 确保给定的根是根结点 moveRootToFront(tab, root); }
- 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
HashMap的balanceInsertion（）
// 插入后的平衡操作 static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) { x.red = true; for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { // 没有结点时 if ((xp = x.parent) == null) { x.red = false; return x; } // 只有两层的树 else if (!xp.red || (xpp = xp.parent) == null) return root; // 左子树插入 if (xp == (xppl = xpp.left)) { if ((xppr = xpp.right) != null && xppr.red) { xppr.red = false; xp.red = false; xpp.red = true; x = xpp; } else { if (x == xp.right) { root = rotateLeft(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; root = rotateRight(root, xpp); } } } } // 右子树插入 else { // 祖父结点不为空，并且颜色为红色时 if (xppl != null && xppl.red) { xppl.red = false; xp.red = false; xpp.red = true; x = xpp; } else { // 左子树插入 if (x == xp.left) { root = rotateRight(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } if (xp != null) { // x 的父亲结点设置成黑色 xp.red = false; if (xpp != null) { // x的祖父结点设置成红色 xpp.red = true; // 左旋 root = rotateLeft(root, xpp); } } } } } }
- 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
HashMap的rotateLeft()
// 红黑树的左旋操作 static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) { // r（right） 指的是调整点的右子树根结点 // pp(parentparent) 是p的祖父结点 // rl(rigthleft) 是p的叔父结点 TreeNode<K,V> r, pp, rl; if (p != null && (r = p.right) != null) { if ((rl = p.right = r.left) != null) rl.parent = p; if ((pp = r.parent = p.parent) == null) (root = r).red = false; else if (pp.left == p) pp.left = r; else pp.right = r; r.left = p; p.parent = r; } return root; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
HashMap的的遍历：
public static void main(String[] args) { Map<String, String> map = new HashMap<String, String>(); map.put("01", "value1"); map.put("02", "value2"); map.put("03", "value3"); //第一种 System.out.println("通过Map.keySet遍历key和value："); for (String key : map.keySet()) { System.out.println("key= "+ key + " and value= " + map.get(key)); } //第二种 System.out.println("通过Map.entrySet使用iterator遍历key和value："); Iterator<Map.Entry<String, String>> it = map.entrySet().iterator(); while (it.hasNext()) { Map.Entry<String, String> entry = it.next(); System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue()); } //第三种：推荐 System.out.println("通过Map.entrySet遍历key和value"); for (Map.Entry<String, String> entry : map.entrySet()) { System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue()); } //第四种 System.out.println("通过Map.values()遍历所有的value，但不能遍历key"); for (String v : map.values()) { System.out.println("value= " + v); } }
- 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
写在最后:头发很小气，不要去说它 - 华仔。
- 1
