type
status
date
slug
summary
tags
category
icon
password
Map的使用
区别于Collection里存储的单列元素，Map里存储的元素是以Key-Value的形式成对出现的，在其他语言中又被称为是字典。主要分类有HashMap / HashTable / Properties / LinkedHashMap / TreeMap
Map在规定泛型时，需要规定Key和Value两个的泛型
Map的常见方法
- put(K k,V v): 如果key不存在，存入键值对；如果key已经存在，会替换原来的value
- get(Object k): 根据key获取到对应的value,如果key不存在，得到的是null
- getOrDefault(Object k,V value): 如果key不存在，使用默认的value值
- remove(K k): 根据key移除键值对
- remove(K k,V v): 根据 key-value键值对删除元素
- putIfAbsent(K k,V v): 如果key不存在，会存入键值对;如果key已经存在，不会覆盖原来的value
- replace(K k,V v): 根据key修改对应的value
- containsKey(k):查询key是否存在
Map
区别与数组、ArrayList等有序集合，Map和Set都是无序的，对于无序的集合，可以通过迭代器来遍历，iterator()，方法定义在Collection里，List和Set都可以使用
Map的特点
- Map元素是无序的，不能通过下标来获取到元素，只能通过 key获取到对应的value
- Map元素的key不允许重复(判断key是否重复的依据),如果重复，后一个key对应的value会覆盖前一个
Map的实现类
HashMap LinkedHashMap TreeMap HashTable Properties
HashTable和HashMap功能类似，区别在于 HashMap是线程不安全的，效率高
HashTable是线程安全的，效率低
Properties 继承自 HashTable,通常用来读取一个文件作为配置项
使用一个对象做为Map的key
Map源代码
HashMap底层使用的是数组+单向链表以及数组+二叉树结构
- 构造方法:
- HashMap(): 空参构造方法,使用默认的加载因子.添加元素时，table的长度是默认长度 16
- HashMap(int initialCapacity): （initialCapacity的长度不一定代表table的程度）table的长度是第一个大于等于 initialCapacity 的 2的n次方的整数
initialCapacity | table的长度 | index（是rehash的后n位） |
3 | 4 | 2 0b100-1 ==> 0b11 |
7 | 8 | 3 0b1000-1 ==> 0b111 |
8 | 8 | 3 |
9 | 16 | 4 |
17 | 32 | 5 |
链表结构在什么情况下会变成树形结构?
思考: 为什么不直接将 table的长度设置为 initialCapacity参数，而要进行计算? table的长度设置为2的倍数，是因为二进制的按位运算rehash的时候的时候方便计算元素的下标
- 成员变量
- float loadFactor: 加载因子
- int threshold: 用来规定数组扩充的条件，阈值 = table的长度 * loadFactor
- Node<K,V> table:数组，用来存储所有的数据.默认是 null,当调用put方法存入数据之前，table才会初始化
- tatic final float DEFAULT_LOAD_FACTOR=0.75f:常量，默认加载因子，是 0.75
- static final int DEFAULT_INITIAL_CAPACITY = 1 << 4:常量16，用来表示table的默认长度
- static final int TREEIFY_THRESHOLD = 8; 用来表示链表在什么情况下会变成二叉树
- static final int MIN_TREEIFY_CAPACITY = 64; 用来表示链表变成成树型结构时，table的最小容量!
TREEIFY_THRESHOLD和MIN_TREEIFY_CAPACITY必须同时满足的时候，链表才会首次转成红黑树型结构
- 常见方法
- put(K k,V v)
链表转为树型结构的时机（同时满足）
- 在同一个位置上，节点的个数大于8,从第9个开始，会尝试将链表转换成为树形结构
- 判断table的长度是否大于等于 MIN_TREEIFY_CAPACITY 64，如果table的长度不够64,会扩容 table 数组为原来的2倍，直到table的长度达到64以后，再把链表变成树形结构
扩容数组的长度的意义在哪儿?
重新分配元素的下标
table数组扩充的时机
- 如果在同一个位置上，存放的元素大于8个，从第9个开始，会尝试变成树形结构。如果此时table的长度不够64,会扩充table数组，将长度变为原来的2倍
- 当元素的个数大于阈值以后，也会扩充table数组 threshold = table.length * loadFactor
HashMap的KV如何判断重复
HashMap的key和HashSet的元素判断是否重复的依据，如果哈希值相同，调用equals方法
元素下标计算的规则: 根据哈希值计算出来的
- 获取到 key的哈希值
- 重算哈希值(怎么重算的，为什么要重算)
- 怎么重算哈希值 hash ^ (hash >> 16) 让哈希值的低位和高位做按位异或运算，得到一个新的值
- 为什么要重算哈希值, rehash后的结果由高位和低位计算出来的，更有代表性，尽可能的减少不同的字符串存入到相同位置的机会
- 计算元素的下标: 拿到重算后的哈希值和 table的长度-1 做按位与运算!
HashTable
和HashMap的底层实现相同，区别是HashTable是线程安全的，效率低
HashTable有一个子类Properties，这个文件法通常是用来加载一个配置项的
Properties prop = new Properties;
- 作者:tacjin
- 链接:http://jin.wiki/article/5b64fe10-9fe4-449d-a745-4335092936c0
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
