Map
1 Map的基本使用
Map(映射)是由Key(键)和Value(值)组成的。每一个键都是不重复的。一个键对应的一个值。键和值在一起称之为键值对。
一个映射是由多个键值对组成的，
将每一个键值对看作一个对象，抽取出一个代表键值对的类-->Map.Entry
- 常用方法
public class TestDemo {
public static void main(String[] args) {
// 创建Map
Map<String,String> map = new HashMap<>();
// 添加元素
map.put("汪峰","章子怡");
map.put("王宝强","马蓉");
map.put("陈羽凡","白百合");
map.put("文章","马伊利");
map.put("华晨宇","张碧晨");
map.put("汪小菲","大S");
// 如果key重复，对应的value会被覆盖
map.put("李小璐","贾乃亮");
map.put("李小璐","pgone");
map.put("周淑怡","pgone");
// 清空集合
// map.clear();
// 根据key获取value
String s = map.get("华晨宇");
System.out.println(s);
// 如果key不存在，会返回null
String s1 = map.get("柯震东");
System.out.println(s1);
// 根据key移除元素,会返回移除掉的value
String s2 = map.remove("王宝强");
System.out.println(s2);
// 判断key是否存在
System.out.println(map.containsKey("周淑怡"));
// 判断value是否存在
System.out.println(map.containsValue("pgone"));
// 返回键值对的集合
Set<Map.Entry<String, String>> entries = map.entrySet();
System.out.println(entries);
// entries.forEach(System.out::println);
// map.forEach(new BiConsumer<String, String>() {
// // s ： key
// // s2 : value
// @Override
// public void accept(String s, String s2) {
// System.out.println(s + s2);
// }
// });
// 快速遍历map
map.forEach((key,value) -> System.out.println(key + " : " + value));
// 判断map是否为空
System.out.println(map.isEmpty());
// 返回所有的key的集合
Set<String> strings = map.keySet();
for (String key : strings) {
String value = map.get(key);
System.out.println(value);
}
// 键值对的个数
int size = map.size();
System.out.println(size);
Collection<String> values = map.values();
System.out.println(values);
System.out.println(map);
practice();
}
// 课堂练习: 输入一个字符串，统计每一个字符出现的次数 aaabbccdd
public static void practice(){
String str = new Scanner(System.in).next();
// 创建Map map的key是字符 map的value是字符出现的次数
Map<Character,Integer> map = new HashMap<>();
// 遍历字符串，获取每一个字符
for (int i = 0; i < str.length(); i++) {
// 获取字符
char c = str.charAt(i);
// 判断字符是否出现
if (map.containsKey(c)){
// 如果存在
Integer integer = map.get(c);
integer += 1;
map.put(c,integer);
}else {
// 首次出现
map.put(c,1);
}
}
map.forEach((key,value) -> System.out.println(key + "出现的次数是" + value));
}
}
2 补充:断点调试
F8 : 执行下一行代码
F9: 跳到下一个断点处
3 HashMap
HashMap是Map接口的实现类，是无序的，key是唯一的。并且key和value都可以为null。是线程不安全的。而且其中的数据位置可能会发生改变。
底层的数据结构是数组 + 链表 + 红黑树
3.1 常用构造方法
// 无参构造，默认底层的数组的初始容量是16，加载因子是0.75F
// 实际上，调用这行无参构造，只会把0.75赋值给加载因子，并没有立即创建长度为16的数组
HashMap() 使用默认初始容量（16）和默认加载因子（0.75）构造一个空 HashMap 。
// 按照指定的初始化容量来创建数组，加载因子是0.75
// 实际上初始化容量在底层经过运算，会变成2的n次方的形式
HashMap(int initialCapacity) 使用指定的初始容量和默认加载因子（0.75）构造一个空 HashMap 。
// 创建HashMap，可以指定初始化容量和加载因子
// 实际上初始化容量在底层经过运算，会变成2的n次方的形式
HashMap(int initialCapacity, float loadFactor) 使用指定的初始容量和加载因子构造一个空 HashMap 。
3.2 底层原码剖析
- 成员变量
// 默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 加载因子
final float loadFactor;
// 扩容的阈值
int threshold;
// HashMap底层的数据
transient Node<K,V>[] table;
// 默认初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 红黑树形成的结点数量
static final int TREEIFY_THRESHOLD = 8;
// 扭转红黑树的数组长度
static final int MIN_TREEIFY_CAPACITY = 64;
- put方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 结点的数组
Node<K,V>[] tab;
// 临时的结点
Node<K,V> p;
// n 数组的长度
// i 数组元素放入的索引
int n, i;
// 当第一次put时，table还是null，会创建长度默认是16的数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 判断数组对应索引处是否有结点
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果没有结点，创建新结点，赋值给i处
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 比较hash和key是否相同
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 如果key相同，替换旧的value
e = p;
else if (p instanceof TreeNode)
// 给红黑数中添加结点
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 如果第一个结点不同，那么继续向下判断剩下的每一个结点，如果有一个相同，就替换value
// 如果都不同,把结点放在链表最后一位
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 判断是否要将链表扭转成红黑树
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 = e;
}
}
if (e != null) { // existing mapping for key
// 如果key相同，将新的value覆盖旧的value，并且返回旧的value
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 实际元素个数 + 1 并且判断是否需要扩容
if (++size > threshold)
resize();// 扩容 会重新分布元素的位置
afterNodeInsertion(evict);
return null;
}
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) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
} // 把老容量 翻倍来进行扩容
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
// 如果还没有数组，指定初始化容量16和阈值 12
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"})
// 创建新的数组
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;
}
总结:
- 当创建HashMap时，会把加载因子赋值为0.75(默认无参构造中)
- 当第一次put时，会创建一个长度为16的Node类型的数组，默认阈值是12.然后根据计算把数组中的某一个索引添加一个Node对象
- 如果key相同，hash值也会相同。会把旧值替换成新值，并且返回旧值
- 如果key不相同，但是hash值相同，会到对应桶的位置进行一个个的逐位比较，直到链表结点的next是null、然后把结点连接在这个链表的最后一位。如果链表长度大于8，并且数组长度 >= 64 会扭转成红黑树。红黑树可以提高查询效率
- 如果链表长度大于8，数组长度小于64,会进行一次扩容。数组长度翻倍，元素位置重新分配、
- HashMap的初始化容量永远是2的n次方的形式
- 扩容是容量翻倍，重新分配的索引要么是原来的索引处，要么是原来索引 + 原来的数组长度 处
- 当扩容时，如果桶上是一个红黑树，经过重新分配后长度 <= 6,会重新扭转成链表
- 注意: HashMap的key一般不要使用自定义的类型。如果要使用，建议重写hashCode方法
public static void main(String[] args) {
// 字符串有可能内容不同，但是hashCode相同
// System.out.println("三个".hashCode());
// System.out.println("上下".hashCode());
HashMap<String,Integer> hashMap = new HashMap<>();
// 当首次添加元素时，会创建一个长度为16的数组，并且把数据放置在某一个桶上面
hashMap.put("1",1000);
// 哈希冲突/碰撞 根据 hash & (n - 1) 的结果重复，就是哈希冲突
// HashMap如何处理hash碰撞?
// 情况一: key的值一样 key的hash值肯定也一样 就会出现hash碰撞
// 结果:新的value替换旧的value,并且返回旧的value
// Integer integer = hashMap.put("1", 2000);
// System.out.println(integer);
// 情况二: key的值不一样 key的hash一样，会出现哈希碰撞
hashMap.put("Ma",3000);
hashMap.put("NB",4000);
// 情况三:key的值不一样， key的hash不一样，但是经过计算的位置重复
hashMap.put("a",5000);
hashMap.put("b",6000);
hashMap.put("c",7000);
hashMap.put("d",5000);
hashMap.put("e",5000);
System.out.println(hashMap);
}
4 Hashtable
特点:
不允许key和value是null,如果是null，抛出空指针异常
默认初始容量是11
默认的扩容是扩大一倍并且 + 1
指定容量给多少就是多少
同步式线程安全的映射
标签：map,hash,映射,value,key,put,null From： https://www.cnblogs.com/460759461-zeze/p/18287664