一.Map
1.特点
- Map 和 Collection 没有继承关系
- Map 以(key,value)的形式存储数据：(键值对),key和value存储的都是对象的内存地址(引用)
2.遍历方式
(1).获取map的KeySet，然后取出Key对应的Value
这种遍历方式效率相对较低，因为他的遍历规则是根据key一个一个的从哈希表中查找value实现的，有两种写法，如下所示
- 写法1：通过循环遍历map.keySet(),取出对应的value
public static void printMap(Map<String,String> map){ if(map.size()==0){ System.out.println("empty map"); } for (String key : map.keySet()) { System.out.println(key+":"+map.get(key)); } } - 写法2：通过迭代器迭代map.keySet()，来取出对应的value
public static void printMap(Map<String,String> map){ Set<String> keySet = map.keySet(); Iterator<String> iterator = keySet.iterator(); while (iterator.hasNext()){ String key = iterator.next(); System.out.println(key+":"+map.get(key)); } }
(2).调用map.entrySet()方法，获取entrySet，然后直接从entrySet中获取Key和value
这种遍历方式是直接从node中获取key，value所以效率较高，比较适用于大数量map的遍历
- 写法1：调用map.entrySet()，然后通过循环遍历entrySet
public static void printMap(Map<String,String> map){ Set<Map.Entry<String, String>> entrySet = map.entrySet(); for (Map.Entry<String, String> entry : entrySet) { System.out.println(entry.getKey()+":"+entry.getValue()); } } - 写法2：调用map.entrySet()，通过迭代器遍历entrySet
public static void printMap(Map<String,String> map){ Set<Map.Entry<String, String>> entrySet = map.entrySet(); Iterator<Map.Entry<String, String>> iterator = entrySet.iterator(); while (iterator.hasNext()){ Map.Entry<String, String> node = iterator.next(); System.out.println(node.getKey() + ":" + node.getValue()); } } - 写法3：直接使用foreach遍历
public static void printMap(Map<String,String> map){ if(map.size()==0){ System.out.println("empty map"); } map.forEach((key,value)->{ System.out.println(key+":"+value); }); }
二.HashMap
1.概述
- HashMap的底层其实是一个数组
- 数组中每个元素是一个单向链表，采用拉链法解决哈希冲突，单链表的每个结点是Node<K,V>类型
- 同一个单链表中所有Node的hash值不一定一样，但是他们所对应的数组下标一定一样(数组的下标是利用 哈希函数/哈希算法根据hash值计算得到的)
- 在JDK1.8之前HashMap是数组和单链表的结合体，在JDK1.8中，加入了红黑树
- 数组的查询效率高，但是增删元素效率较低
- 单链表在随机增删元素方面效率较高，但是查询效率较低
- 链表过长会严重影响HashMap的性能，红黑树的结构可以快速增删改查
- HashMap将它们相结合，充分利用了它们各自的优点
2.特点
- HashMap是无序且不可重复的
- HashMap只允许存储一条记录为null的键，允许多条记录的值为null。
- HashMap是非线程安全的，如果要满足线程安全，可以用Collections的synchronizedMap使HashMap具有线程安全的能力，或者使用ConcurrentHashMap
- HashMap在JDK1.8之前底层次采用数组+链表的形式，在JDK1.8时新增了红黑树部分
3.参数
//默认初始化容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量2^30
static final int MAXIMUM_CAPACITY = 1 << 30
//加载因子为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表转为红黑树的阈值为8
static final int TREEIFY_THRESHOLD = 8;
//红黑树转为链表的阈值为6
static final int UNTREEIFY_THRESHOLD = 6;
//最小树型化阈值为64
static final int MIN_TREEIFY_CAPACITY = 64;
//存储元素的容器
transient Node<K,V>[] table;
//key-value的个数
transient int size;
//操作次数
transient int modCount;
//能容纳最多Key-value的个数
int threshold;(1).DEFAULT_INITIAL_CAPACITY(默认初始化容量)
①.容量为什么是2的n次幂呢
- HashMap的数组是hash表，计算散列值的时候会有取模运算(hash%length)，但是取模运算相对比较耗时，所以采用的是hash&(length-1)的方式，而hash%length==hash&(length-1)的前提是length是2的n次幂。
- 当length为2的n次幂时，发生hash冲突的概率会小很多，空间利用率也会变高，例如：
当长度为9时： 3&(9-1)=0 2&(9-1)=0 都在0上发生hash冲突 当长度为8时： 3&(8-1)=3 2&(8-1)=2 不同位置上，不发生hash冲突
②.如果实例化传入的值不是2的n次幂会怎么样
如果创建HashMap时，给定的number不是2的n次幂，那么会通过以下方法，计算找到大于等于number的最小2次幂的数
static final int tableSizeFor(int cap) {
//使用cap-1是为了避免传入的cap值本身就是2的n次幂而做的处理
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
//容量最大也就是32bit的正数，因此最后只需要n|=n>>>16即可，最多也就32个1，在构造函数调用方法的时候其实已经做了判断了。
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
//代码分析
cap = 13; // 计算过程（二进制）
n = cap-1; 0000 1100
———————————————————————————————————————————————
n |= n>>>1; 0000 1100 | 0000 0110
————————————————————
0000 1110
———————————————————————————————————————————————
n |= n>>>2; 0000 1110 | 0000 0011
————————————————————
0000 1111
———————————————————————————————————————————————
n |= n>>>4; 0000 1111 | 0000 0000
————————————————————
0000 1111
———————————————————————————————————————————————
n |= n>>>16; 0000 1111 | 0000 0000
————————————————————
0000 1111
———————————————————————————————————————————————
//n等于15，既不小于0，也不大于最大容量所以返回n+1
n = n + 1 0000 1111 + 0000 0001
————————————————————
0001 0000 = 16以上一系列运算的目的，就是将cap-1的二进制有效位全部变成1，最后再用这个些有效位为1的二进制数+1就变成了大于等于传入容量最小2的n次幂的数。
(2).MAXIMUM_CAPACITY(最大容量)
①为什么最大容量是2^30
- 满足容量为2的n次幂的特点
- int类型是32bit，占4个字节。
- Java的原始类型里没有无符号类型，所以首位是符号位 正数为0，负数为1。
- Java中存放的是补码，1左移31位代表的是-2147483648，所以最大只能到30。
(3).DEFAULT_LOAD_FACTOR(默认加载因子)
①加载因子是什么
这个加载因子表示的是hash表中元素填满的程度，加载因子越大，能填充的元素就越多。
- 加载因子越大，空间利用率就越高，产生hash冲突的机会也会随之加大。
- 加载因子越小，空间利用率就越低，产生hash冲突的机会也会随之减小。
②加载因子的作用
在当前数组长度达到容量的75%时，就会触发扩容操作
③为什么需要加载因子
在JDK1.8之前，使用的数组+链表的实现方式，通过计算hash，找到数组中对应的位置，如果已经存在元素，就加到这个位置的链表上。
在JDK1.8之后，链表过长还会转为红黑树，红黑树相较于原来的链表，占用的空间会多出近一倍，但是查询速度确快了非常多，属于是用空间换时间，将链表转红黑树，是一个耗时的操作，但是一个高效率的hash表内部的链表不应该过长。
如果数组的很多元素上面都有值了，那么需要对这个数组扩容，这个过程就是resize，这个resize是一个非常耗时的操作，为了选择一个合适的时机来触发。
④为什么是0.75
在不同的场景下，考虑的方面不同，不同的语言的defaultLoadFactor都不一样，比如java的是0.75，而Go是0.65，Python中确是0.762，可以参考一下《HashMap的loadFactor为什么是0.75》
取0.75的真正原因在源码中其实是有注释说明的
<p>As a general rule, the default load factor (.75) offers a good
tradeoff between time and space costs. Higher values decrease the
space overhead but increase the lookup cost (reflected in most of
the operations of the <tt>HashMap</tt> class, including
<tt>get</tt> and <tt>put</tt>). The expected number of entries in
the map and its load factor should be taken into account when
setting its initial capacity, so as to minimize the number of
rehash operations. If the initial capacity is greater than the
maximum number of entries divided by the load factor, no rehash
operations will ever occur.大概意思就是：加载因子太小浪费空间且会发生更多次数的rehash，太大的话会增加hash冲突，所以0.75是一个折中的选择。
(4).TREEIFY_THRESHOLD(链表转为红黑树阈值)
①.为什么Map桶中个数超过8才转为红黑树
源码中也给出了解释
Because TreeNodes are about twice the size of regular nodes, we
use them only when bins contain enough nodes to warrant use
(see TREEIFY_THRESHOLD). And when they become too small (due to
removal or resizing) they are converted back to plain bins. In
usages with well-distributed user hashCodes, tree bins are
rarely used. Ideally, under random hashCodes, the frequency of
nodes in bins follows a Poisson distribution
(http://en.wikipedia.org/wiki/Poisson_distribution) with a
parameter of about 0.5 on average for the default resizing
threshold of 0.75, although with a large variance because of
resizing granularity. Ignoring variance, the expected
occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
factorial(k)). The first values are:
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million这段内容说到，hashcode离散性很好的时候，树型bin用到的概率非常小，因为数据均匀分布在每个bin中，几乎不会有bin中链表长度会达到阈值。
但是在随机hashcode下，离散性可能会变差，而JDK又不能阻止用户实现这种不好的hash算法，因此可能导致不均匀的数据分布。
不过理想情况下，随机的hashcode算法下所有的bin中的结点分布频率会遵循泊松分布，注释中也列出来了，链表长度到达8的概率为0.00000006，几乎是不可能事件，所以才选择8作为阈值。
(5).UNTREEIFY_THRESHOLD(红黑树转为链表阈值)
①.为什么阈值为6
如果阈值为7，当我们频繁的添加和删除操作时，会造成红黑树和链表的频繁转换，影响性能。
(6).MIN_TREEIFY_CAPACITY(最小树型化阈值)
①.作用
当数组中结点大于TREEIFY_THRESHOLD，但是整个哈希表的容量小于MIN_TREEIFY_CAPACITY时，只会扩容，不会变成红黑树，只有在哈希表的容量大于MIN_TREEIFY_CAPACITY并且数组中结点大于TREEIFY_THRESHOLD时，才会转为红黑树。
②.为什么取64
The smallest table capacity for which bins may be treeified.
(Otherwise the table is resized if too many nodes in a bin.)
Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
between resizing and treeification thresholds.注释中有提到，MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍，但是转为红黑树的阈值是8，也就说MIN_TREEIFY_CAPACITY的值最少应该为32，这里设置成64的原因可能是等到数组扩容到了32后再扩容一次后才会开始触发树型化。
4.构造器
HashMap一共有4个构造器。
(1).常用构造器
使用该构造器如果用户没有传入initialCapacity 和loadFactor这两个参数，会使用默认值。
initialCapacity默认为16，loadFactory默认为0.75
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的n次幂的数替代
this.threshold = tableSizeFor(initialCapacity);
}(2).指定容量的构造器
可以指定长度，加载因子使用默认的0.75；
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}(3).采用默认参数的构造器
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}(4).拷贝构造器
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}5.内部方法
(1).putMapEntries方法
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
//传入的map大小不能是0
if (s > 0) {
//如果还没有存储过任何元素，才能进入，如果已经存储过元素会直接触发resize
if (table == null) { // pre-size
/*
先不考虑容量是否为2的幂，先算出容器的容量
因为转为了float，算出来的数会有小数，直接上取整，所以做了个+1的操作
*/
float ft = ((float)s / loadFactor) + 1.0F;
/*
如果小于最大容量，那么直接将该值取为整型，然后使用
如果大于最大容量，就赋值为最大容量
*/
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
/*
上面的操作已经确定好了容量的大概数值
因为容量要求是2的次幂，这里再根据刚刚得到的大小，
找到一个大于等于这个容量的2次幂作为真正的容量
*/
if (t > threshold)
threshold = tableSizeFor(t);
}
/*
如果能到这里，说明已经初始化过了，
这里判断传入的map大小，是否已经大于当前存储的最大值了
*/
else if (s > threshold)
//如果传入map的大小大于了存储最大值，那么必须先进行扩容
resize();
//循环调用putVal存入元素，putVal方法里面也可以进行扩容
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);
}
}
}总结：
- 如果当前的HashMap是空的，那么会先确定插入后HashMap的容量
- 如果当前的HashMap不是空的，会先判断是否需要resize
- 插入元素就是获取到所有的key-value循环调用putVal方法
(2).putVal方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
/*
tab是当前HashMap的数组
p是要操作的Node
n是当前HashMap的Node数组长度
i是操作的数组下标
*/
Node<K,V>[] tab; Node<K,V> p; int n, i;
/*
这里的操作是判断HashMap是否是空的
同时，把HashMap的table赋值给了tab
将HashMap的长度赋值给了n
*/
if ((tab = table) == null || (n = tab.length) == 0)
//调用resize，生成了一个tab数组，并且获取了他的长度
n = (tab = resize()).length;
/*
(n-1)&hash 其实就是一个取模运算相当于hash%n
根据hash找到数组中的索引位置
*/
if ((p = tab[i = (n - 1) & hash]) == null)
/*
当数组中当前位置没有元素的时候
会在这个位置实例化一个元素作为这个位置中的第一个元素
*/
tab[i] = newNode(hash, key, value, null);
else {
//进入到这里说明数组中有元素了，需要处理hash冲突
Node<K,V> e; K k;
//如果数组中当前位置的第一个元素的key与新插入的元素的key相同
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//将e指向p
e = p;
else if (p instanceof TreeNode)
//如果已经树化，调用putTreeVal插入方法插入
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//如果还没有被树化，还是链表
else {
for (int binCount = 0; ; ++binCount) {
/*
遍历到链表尾部，如果没有发现相同的key结点，采用尾插法插入元素
因为插入了一个新的元素，所以要判断一下当前链表的长度
如果超过阈值，就会转为红黑树
*/
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果数组中有元素的key与新插入的key完全相同，用e指向p
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
/*
通过上面的操作，如果map中有相同的key
我们将e指向该结点
如果e是空的，说明成功插入了
如果e不是空的，就把e的value最为旧值返回，将新插入的value保存进去
*/
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//hashmap的afterNodeAccess是个空函数，LinkedHashMap实现了他
afterNodeAccess(e);
return oldValue;
}
}
//操作次数++
++modCount;
//插入后size会+1，并且判断数组长度，是否需要resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}总结：
- 如果当前的HashMap是空的，会进行一次resize
- 如果两个key相同，会用新值覆盖旧值
- 新增元素在链表中采用的是尾插法
- 在新增了一个元素后，都会通过size进行一次resize判断
(3).resize方法
final Node<K,V>[] resize() {
//首先保存旧的数组
Node<K,V>[] oldTab = table;
//获取旧数组的长度，如果是空的就为0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//获取扩容前HashMap的容量
int oldThr = threshold;
/*
newCap：新数组的长度
newThr：新HashMap的最大容量
*/
int newCap, newThr = 0;
//判断旧HashMap是否存入了元素
if (oldCap > 0) {
//旧数组的长度大于等于最大容量，阈值就会设置为Integer的最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
/*
首先，新容量会设置为旧容量的两倍
然后，判断扩容后的新容量是否<2^30
并且旧容量是否>=16
*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//以上条件都满足的话，阈值也会翻倍
newThr = oldThr << 1; // double threshold
}
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"})
/*
通过上面的操作，已经确定好了容量和扩容阈值
1.如果扩容前的HashMap没有存入元素，就按照默认值进行扩容
2.如果扩容前的HashMap已经存入了元素，直接扩容两倍，如果旧数组的长度大于了16，那么threshold也扩大两倍
3.如果此时的数组长度已经到了HashMap的最大容量时，会将threshol设置为Integer的最大值
*/
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;
//将原来map中不是null的元素rehash后再放到新的数组中
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果当前位置就一个元素，那么直接放到新数组里面
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
/*
这里表示这个位置不止一个结点
判断这个结点是否已经树型化了
如果已经树型化，将这个树上的结点rehash后存入
*/
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;
/*
如果是true,表示(e.hash&(newCap-1))还会和(e.hash&(oldCap-1))一样
因为新容量是旧容量的两倍，而容量都是2的次幂
所以说新容量就是旧容量的二进制位高位左移了一位
那(e.hash & oldCap) == 0 就代表(e.hash & (newCap-1)) = (e.hash & (oldCap-1))
这就意味着该元素在新数组中的位置不会变，因此，将其组成一个链表即可
*/
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
/*
而对于非0的key，那他的位置在新数组中需要更新，就需要在新的位置再组合链表
*/
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;
}(4).put方法
HashMap的put方法实现了Map的put接口，其实现也是调用的HashMap的putVal方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}(5).containsKey方法
此方法用来判断key是否存在，在查找前必须满足三个条件
- (tab=table)!=null 数组不能为空
- (n=tab.length)>0 数组长度大于0
- （first = tab[(n-1)&hash]）!=null 头结点不为空
只有以上三个条件都满足了才可能存在待查找的元素，否则返回null
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
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;
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;
}三.TreeMap
1.概述
- TreeMap的底层通过红黑树实现
- TreeMap的迭代器采用的是中序遍历的方式
2.红黑树简介
红黑树又称红-黑二叉树，它首先是一颗二叉树，它具有二叉树的所有特性，同时红黑树更是一颗自平衡的排序二叉树
(1).平衡二叉树的特性：
1.是一颗空树或它的左右两个子树的高度差绝对值不超过1。
2.左右两个子树都是平衡二叉树。
(2).红黑树的规则：
- 每个节点都只能是红色或者黑色。
- 根结点是黑色。
- 每个叶结点(NIL结点，空结点)是黑色的。
- 如果一个结点是红色的，那个它的两个子结点都是黑色的，一条路径上不能出现相邻的两个红色结点。
- 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
3.特点
- TreeMap存储是无序的
- TreeMap不允许重复存入相同的元素
- TreeMap可以排序
4.排序规则
- TreeMap中key可以自动对String类型或8大基本数据类型的包装类进行排序
- TreeMap无法直接对自定义类型进行排序
5.自定义类型如何排序
如果直接将自定义类型添加到TreeMap中，key会报 java.lang.ClassCastException
原因：自定义没有实现 java.lang.Comparable 接口(此时，使用的是TreeMap的无参构造器)，如果想要排序，必须要指定排序规则，主要有以下两种解决办法
(1).方法一
放在集合中的自定义类型实现 java.lang.Comparable 接口，重写 compareTo 方法。
public class cat implements Comparable<cat>{
int age ;
public cat(int age){
this.age = age;
}
@Override
public int compareTo(cat c) {
//按照年龄升序排序
return this.age-c.age;
}
}(2).方法二
选择带比较器参数的构造器，并重写比较器中的 compare方法。
如果采用这种方式，在传递比较器参数给构造器时有以下3种写法
-
定义一个 Comparator 接口的实现类
//自定义Cat类 public class cat{ int age ; public cat(int age){ this.age = age; } } //接口实现类 class MyCat implements Comparator<Cat>{ @Override public int compare(Cat o1, Cat o2) { return o1.age-o2.age; } } //创建可排序的TreeMap public static void main(String[] args) { TreeMap<Cat, Object> TreeMap = new TreeMap<>(new MyCat()); } -
使用匿名内部类
//自定义Cat类 public class cat{ int age ; public cat(int age){ this.age = age; } } //创建TreeMap public static void main(String[] args) { TreeMap<Cat, Object> TreeMap = new TreeMap<>(new Comparator<Cat>() { @Override public int compare(Cat o1, Cat o2) { return o1.age - o2.age; } }); } -
使用lambda表达式(Comparator是函数式接口)
//自定义Cat类 public class cat{ int age ; public cat(int age){ this.age = age; } } //创建TreeMap public static void main(String[] args) { TreeMap<Cat, Object> TreeMap = new TreeMap<>((o1,o2)->o1.age-o2.age); } //或者是 public static void main(String[] args) { TreeMap<Cat, Object> TreeMap = new TreeMap<>(Comparator.comparingInt(o -> o.age)); }
(3).如何选择解决方案
- 当比较规则不会发生改变，或者比较规则只有一个时，建议使用方法一
- 当比较规则有多个，并且需要在多个规则中切换时，建议使用方法二
6.内部参数
//排序用的比较器
private final Comparator<? super K> comparator;
//头结点
private transient Entry<K,V> root;
//大小
private transient int size = 0;
//修改次数
private transient int modCount = 0;7.put方法
public V put(K key, V value) {
//首先获取到头结点
Entry<K,V> t = root;
//如果头结点是空的，调用比较器，检查key是不是空的
if (t == null) {
compare(key, key); // type (and possibly null) check
//因为头结点是空的，所以把这个结点保存为头结点
//因为没有父结点，所以传入了一个null
root = new Entry<>(key, value, null);
//长度增加到了1
size = 1;
//操作次数++
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
//获取内部的比较器
Comparator<? super K> cpr = comparator;
//如果比较器不是空，按着比较器的规则执行
if (cpr != null) {
do {
//将根节点赋值给parent
parent = t;
//比较key与根节点的大小
cmp = cpr.compare(key, t.key);
if (cmp < 0)
//如果key<根节点的key，指向左子树
t = t.left;
else if (cmp > 0)
//如果key>根节点的key，指向右子树
t = t.right;
else
//如果相同覆盖value
return t.setValue(value);
} while (t != null);
}
//没有设置比较器，采用自然排序规则
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
//强制类型转换
Comparable<? super K> k = (Comparable<? super K>) key;
do {
//此处与上方逻辑一致
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
//创建一个新的结点，并指定父节点
Entry<K,V> e = new Entry<>(key, value, parent);
//根据比较结果，决定新结点为父节点的左孩子还是右孩子
if (cmp < 0)
parent.left = e;
else
parent.right = e;
//新插入结点后需要重新调整红黑树
fixAfterInsertion(e);
size++;
modCount++;
return null;
}总结：
- TreeMap的put方法主要分为构建排序二叉树和平衡二叉树两个步骤
- 添加结点的过程如下
- 以根节点为初始结点进行检索
- 通过比较器，与当前结点进行比较，如果新增结点值比较大，那么就以当前结点的右子结点作为新的当前结点，否则以左子结点作为新的当前结点
- 找到合适的叶子结点后，将新增结点与该结点比较，如果新增结点大，则添加为右子结点，否则为左子结点
四.LinkedHashMap
1.概述
HashMap和双向链表结合在一起就是LinkedHashMap,它是一个将所有结点链入一个双向链表HashMap,因其是HashMap的子类，所以它自然拥有HashMap的所有特性。
2.特点
LinkedHashMap增加了时间和空间上的开销，但是它通过维护一个额外的双向链表保证了数据的插入顺序。
Comments | NOTHING