双列集合
键值对 一一对应
键值对对象 entry
Map
Put第一次给不存在的key，会把键值对添加到map中，返回null
Put给同一个key是会覆盖value的，返回被覆盖的值value
Remove根据key删除键值对，返回被删除的值value
Map遍历
键找值
把所有键放到单列集合中map.keyset()方法，获取每一个键，再调用map.get(key)获取每一个值
键值对
Map.entryset()获得每一键值对，放到一个set集合中
Map.Entry<string,string>：因为Entry是Map里的一个接口，所以在用Entry接口的时候，要用Map调用
Entry.getkey() Entry.getvalue() 分别获取key和value
Lambda遍历
Foreach
写一个匿名内部类实现biconsumer接口，创建这个匿名内部类的对象
Hashmap
但是计算哈希值的时候，只会利用键计算哈希值，和值无关
键是自定义对象，要重写hashcode和equals方法，值的话就不用
package exercise;
import java.util.*;
public class exercise3 {
public static void main(String[] args) {
String[] arr = {"A", "B", "C", "D"};
ArrayList<String> list = new ArrayList<>();
Random r = new Random();
for (int i = 0; i < 80; i++) {
list.add(arr[r.nextInt(arr.length)]);
}
HashMap<String,Integer> hm = new HashMap<>();
for (String s : list) {
if (hm.containsKey(s)) {
Integer i = hm.get(s);
i++;
hm.put(s, i);
} else {
hm.put(s, 1);
}
}
System.out.println(hm);
//求最大值
int max = 0;
Set<Map.Entry<String, Integer>> entries = hm.entrySet();
for (Map.Entry<String, Integer> entry : entries) {
if (entry.getValue() > max) {
max = entry.getValue();
}
}
//把和最大值相同的景点打印
for (Map.Entry<String, Integer> entry : entries) {
if (entry.getValue() == max) {
System.out.println(entry.getKey());
}
}
}
}Linkedhashmap
Treemap
按照键进行排序
package exercise;
import java.util.TreeMap;
public class exercise4 {
public static void main(String[] args) {
String str = "aababcabcdabcde";
TreeMap<Character, Integer> ts = new TreeMap<>();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (ts.containsKey(c)) {
Integer j = ts.get(c);
j++;
ts.put(c, j);
} else {
ts.put(c, 1);
}
}
StringBuilder sb = new StringBuilder();
ts.forEach((character, integer) -> sb.append(character).append(" (").append(integer).append(") "));
System.out.print(sb);
}
}Hashmap的底层源码
→：是继承自Map的方法
↑：重写Map里的方法
m：是方法（同名就是构造方法，不同名就是成员方法）
f：是成员属性，可能是变量或常量
i:接口
c：内部类
Hashmap中每一个元素都是Node对象，实现entry接口
Hash：记录哈希值
Key：键
Value：值
Next：记录下一个node的地址值
Hashmap中的红黑树
Parent：父节点
Left：左子结点
Right：右子节点
Red：ture就是红色，false就是黑
Table：记录数组的地址值，装的就是每一个node对象
默认数组初始容量16
默认加载因子0.75
Hashmap最大容量2^30
Hashmap在调用空参构造的时候，底层的数组还没有创建，默认null
只是指定了加载因子为0.75
直到put的时候才真正建立数组
Hash(key)：根据键计算出哈希值
onlyifAbsent：当前的数据是否保留，false就是不保留（当新的元素添加，键相同时，值就会覆盖掉原来的）
Hashmap添加元素源码分析
Hashmap添加第一个元素
数组位置为null
Putval
Resize（）：第一次添加元素，就会在这个方法里创建新的数组
第二种情况
数组位置不为null，键不重复，挂在下面形成链表或者红黑树
第三种情况
数组位置不为null，键重复，元素覆盖
这里会直接break
走这里
把新元素的值赋值给老元素的键值对的值
Treemap源码
添加第一个元素
//表示两个元素的键比较之后的结果
int cmp;
//表示当前要添加节点的父节点
Entry<K,V> parent;
//表示当前的比较规则
//如果我们是采取默认的自然排序，那么此时comparator记录的是null，cpr记录的也是null
//如果我们是采取比较去排序方式，那么此时comparator记录的是就是比较器
Comparator<? super K> cpr = comparator;
//表示判断当前是否有比较器对象
//如果传递了比较器对象，就执行if里面的代码，此时以比较器的规则为准
//如果没有传递比较器对象，就执行else里面的代码，此时以自然排序的规则为准
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else {
V oldValue = t.value;
if (replaceOld || oldValue == null) {
t.value = value;
}
return oldValue;
}
} while (t != null);
} else {
//把键进行强转，强转成Comparable类型的
//要求：键必须要实现Comparable接口，如果没有实现这个接口
//此时在强转的时候，就会报错。
Comparable<? super K> k = (Comparable<? super K>) key;
do {
//把根节点当做当前节点的父节点
parent = t;
//调用compareTo方法，比较根节点和当前要添加节点的大小关系
cmp = k.compareTo(t.key);
if (cmp < 0)
//如果比较的结果为负数
//那么继续到根节点的左边去找
t = t.left;
else if (cmp > 0)
//如果比较的结果为正数
//那么继续到根节点的右边去找
t = t.right;
else {
//如果比较的结果为0，会覆盖
V oldValue = t.value;
if (replaceOld || oldValue == null) {
t.value = value;
}
return oldValue;
}
} while (t != null);
}
//就会把当前节点按照指定的规则进行添加
addEntry(key, value, parent, cmp < 0);
return null;
private void addEntry(K key, V value, Entry<K, V> parent, boolean addToLeft) {
Entry<K,V> e = new Entry<>(key, value, parent);
if (addToLeft)
parent.left = e;
else
parent.right = e;
//添加完毕之后，需要按照红黑树的规则进行调整
fixAfterInsertion(e);
size++;
modCount++;
}
private void fixAfterInsertion(Entry<K,V> x) {
//因为红黑树的节点默认就是红色的
x.color = RED;
//按照红黑规则进行调整
//parentOf:获取x的父节点
//parentOf(parentOf(x)):获取x的爷爷节点
//leftOf:获取左子节点
while (x != null && x != root && x.parent.color == RED) {
//判断当前节点的父节点是爷爷节点的左子节点还是右子节点
//目的：为了获取当前节点的叔叔节点
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//表示当前节点的父节点是爷爷节点的左子节点
//那么下面就可以用rightOf获取到当前节点的叔叔节点
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
//叔叔节点为红色的处理方案
//把父节点设置为黑色
setColor(parentOf(x), BLACK);
//把叔叔节点设置为黑色
setColor(y, BLACK);
//把爷爷节点设置为红色
setColor(parentOf(parentOf(x)), RED);
//把爷爷节点设置为当前节点
x = parentOf(parentOf(x));
} else {
//叔叔节点为黑色的处理方案
//表示判断当前节点是否为父节点的右子节点
if (x == rightOf(parentOf(x))) {
//表示当前节点是父节点的右子节点
x = parentOf(x);
//左旋
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
//表示当前节点的父节点是爷爷节点的右子节点
//那么下面就可以用leftOf获取到当前节点的叔叔节点
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
//把根节点设置为黑色
root.color = BLACK;
}
**************************
6.课堂思考问题：
6.1TreeMap添加元素的时候，键是否需要重写hashCode和equals方法？
此时是不需要重写的。
6.2HashMap是哈希表结构的，JDK8开始由数组，链表，红黑树组成的。
既然有红黑树，HashMap的键是否需要实现Compareable接口或者传递比较器对象呢？
不需要的。
因为在HashMap的底层，默认是利用哈希值的大小关系来创建红黑树的
6.3TreeMap和HashMap谁的效率更高？
如果是最坏情况，添加了8个元素，这8个元素形成了链表，此时TreeMap的效率要更高
但是这种情况出现的几率非常的少。
一般而言，还是HashMap的效率要更高。
6.4你觉得在Map集合中，java会提供一个如果键重复了，不会覆盖的put方法呢？
此时putIfAbsent本身不重要。
传递一个思想：
代码中的逻辑都有两面性，如果我们只知道了其中的A面，而且代码中还发现了有变量可以控制两面性的发生。
那么该逻辑一定会有B面。
习惯：
boolean类型的变量控制，一般只有AB两面，因为boolean只有两个值
int类型的变量控制，一般至少有三面，因为int可以取多个值。
6.5三种双列集合，以后如何选择？
HashMap LinkedHashMap TreeMap
默认：HashMap（效率最高）
如果要保证存取有序：LinkedHashMap
如果要进行排序：TreeMap
![[NOIP1998 提高组] 拼数](https://img-blog.csdnimg.cn/direct/667a8d08e2df436982d3986eec37d18c.png#pic_center)
