概述
对 JAVA
的集合框架中的 Map
下的一些子类相关的原理以及应用进行复盘。
目录
主要内容
0x01:概述
Map: 双列数据,存储 key-value
对的数据
-
HashMap:作为
Map
的主要实现类;线程不安全的,效率高;存储null
的key
和value
-
LinkedHashMap
:保证在遍历map元素时,可以按照添加的顺序实现遍历。
原因:在原有的HashMap底层结构基础上,添加了一对指针,指向前一个和后一个元素。
对于频繁的遍历操作,此类执行效率高于HashMap。
-
-
TreeMap:保证按照添加的
key-value
对进行排序,实现排序遍历。此时考虑key
的自然排序或定制排序 -
Hashtable:作为古老的实现类;线程安全的,效率低;不能存储
null
的key
和value
- Properties:常用来处理配置文件。
key
和value
都是String
类型
- Properties:常用来处理配置文件。
HashMap 的底层结构:
-
jdk7
及之前:数组+链表 -
jdk8
:数组+链表+红黑树
Map的基础树如下图
0x02:对Map中的结构理解
-
Map中的
key
是无序的,不可重复的,使用Set
储存所有的key-
在实际开发中,key的值可能是我们自定义的一个类型,所以要求 key 所在的类需要重写
equals()
和hashCode()
方法以HashMap为例
-
-
Map中的
value
是无序的,可重复的,使用Collection储存所有的value -
value所在类需要重写
equals()
-
Map中的
entry
:无序的、不可重复的,使用Set储存所有的entry
对象一个键值对:key-value构成了一个Entry对象
如下图所示
0x03:浅谈HashMap底层原理
我们先以 jdk7
为例
HashMap map = new HashMap()
在实例化以后,底层创建了长度为 16
的以为数组 Entry[] table
如下代码
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
向 map 存入数据
map.put("key1","value1")
存入数据的过程如下:
1、在向map存入数据时,首先会调用 key1
所在类的 hashCode()
计算key1哈希值,此哈希值经过某种算法计算以后,得到在 Entry
数组中的存放位置,如下
public V put(K key, V value) {
//省略....
int hash = hash(key);
//通过hash计算得到一个数组的索引坐标
int i = indexFor(hash, table.length);
//省略...
}
上述代码摘自 JDK7 中的 HashMap源码
2、如果此位置上的数据为空,此时的 key1-value1
添加成功。(情况1)
3、如果此位置上的数据不为空 (意味着此位置上存在一个或多个数据 (以链表形式存在) , 则开始比较 key1
和已经存在的一个或多个数据的哈希值
- 如果
key1
的哈希值与已经存在的数据的哈希值都不相同,此时key1-value1
添加成功 (情况2) - 如果key1的哈希值和已经存在的某一个数据 (key2-value2) 的哈希值相同,继续比较:调用
key1
所在类的equals(key2)
方法,比较:- 如果
equals()
返回false
: 此时key1-value1
添加成功。(情况3) - 如果
equals()
返回true
: 使用value1
替换value2
。
- 如果
源码如下
//摘自JDK7中的HashMap源码中的部分代码实现
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key);
//通过hash计算得到一个数组的索引坐标
int i = indexFor(hash, table.length);
//如果计算得出的位置不为空,呈现为链表的结构,开始遍历
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//情况2、3
if (e.hash == hash && ((k = e.key) == key || key.equals(k))){
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//如果此位置上的数据为空,直接添加 (情况1)
addEntry(hash, key, value, i);
return null;
}
补充:关于 “情况2” 和 “情况3”:此时 key1-value1
和原来的数据以链表(单向)的方式存储。
/**
* Like addEntry except that this version is used when creating entries
* as part of Map construction or "pseudo-construction" (cloning,
* deserialization). This version needn't worry about resizing the table.
*
* Subclass overrides this to alter the behavior of HashMap(Map),
* clone, and readObject.
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
//将当前的数据作的内存地址储存到自身的next中,实现单向链表的方式储存
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
在不断的添加过程中,会涉及到扩容问题,当超出临界值 (且要存放的位置非空) 时,扩容。
-
默认的扩容方式:扩容为原来容量的
2
倍,并将原有的数据复制过来。部分源码如下/** * Adds a new entry with the specified key, value and hash code to * the specified bucket. It is the responsibility of this * method to resize the table if appropriate. * * Subclass overrides this to alter the behavior of put method. */ void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { //扩容至原来的两倍 resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); }
而 “jdk8” 相较于 “jdk7” 在底层实现方面的不同,以下列出常见的
-
new HashMap(): 底层没有马上创建一个长度为
16
的数组,而是在首次调用put()
方法时,底层创建长度为16的数组HashMap
空参的构造方法,相较于JDK7
中的实现/** * 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 }
而 JDK8 中,在调用 put 时,会先调用 putVa() 方法,再由 putVal 内部进行一些逻辑判断,发现当前为首次调用,则再进行调用 resize() 对数组进行初始化,长度为
16
。 -
jdk8
底层的数组是:Node[],而非Entry[] -
jdk7
底层结构只有:数组+链表。而jdk8
中底层结构:数组+链表+红黑树。- 形成链表时,”七上八下“( jdk7: 新的元素指向旧的元素。jdk8:旧的元素指向新的元素)
- 当数组的某一个索引位置上的元素以链表形式存在的数据个数
> 8
且当前数组的长度> 64
时,此时此索引位置上的所数据改为使用 "红黑树" 存储。
HashMap源码中的重要常量
-
DEFAULT_INITIAL_CAPACITY
: HashMap的默认容量,16 -
DEFAULT_LOAD_FACTOR
:HashMap的默认加载因子:0.75-
为什么是 0.75 ?
提前扩容的原因:在数组中预留一些空的索引位置,可以使链表和树形结构出现的数量更少,并且还要兼顾数组索引位置的利用率,所以 “加载因子” 定为
0.75
可以使得到一个恰好的扩容临界值,同时兼顾上述的两者。
-
-
threshold
:扩容的临界值,容量 * 填充因子
:16 * 0.75 => 12
-
TREEIFY_THRESHOLD
:Bucket 中链表长度大于该默认值,转化为红黑树:8
-
MIN_TREEIFY_CAPACITY
:桶中的Node
被树化时最小的hash
表容量:64
拓展
看到这里,我们在回到 HashSet
的源码实现中去看,向 HashSet
存入数时将写入的值存到了 HashMap 中的 key 的位置
而 Value
的位置则使用一个常量进行填充,常量的值为一个空的 Object
对象常量,并且是静态的(只会被创建一次,所有的value都指向同一个),如下代码
所以由此可知,HashSet 实际的底层是使用 HashMap 来进行储存实际上底层是使用 HashMap
去储存的。
0x04:浅谈LinkedHashMap的底层原理
LinkedHashMap 是 HashMap
的子类
在 HashMap
存储结构的基础上,使用了一对双向链表来记录添加元素的顺序,并重写了 HashMap
中的 newNode
方法,如下代码
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
在 LinkedHashMap 新增了一个类 Entry
,并继承了 HashMap.Node
,增加了双向链表的特性,如下代码
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
与 LinkedHashSet
类似, LinkedHashMap 可以维护 Map 的迭代顺序:迭代顺序 与 Key-Value
对的插入顺序一致
0x05:Map接口常用的方法
添加、删除、修改操作:
-
Object put(Object key,Object value)
:将指定key-value添加到(或修改)当前map对象中
-
void putAll(Map m)
:将m中的所有key-value对存放到当前map中
-
Object remove(Object key)
:移除指定key的key-value对,并返回value
-
void clear()
:清空当前map中的所有数据
测试代码
@Test
public void test3(){
Map map = new HashMap();
//添加
map.put("AA",123);
map.put(45,123);
map.put("BB",56);
//修改
map.put("AA",87);
System.out.println(map);
Map map1 = new HashMap();
map1.put("CC",123);
map1.put("DD",123);
map.putAll(map1);
System.out.println(map);
//remove(Object key)
Object value = map.remove("CC");
System.out.println(value);
System.out.println(map);
//clear()
map.clear();//与map = null操作不同
System.out.println(map.size());
System.out.println(map);
}
输出结果
{AA=87, BB=56, 45=123}
{AA=87, BB=56, CC=123, DD=123, 45=123}
123
{AA=87, BB=56, DD=123, 45=123}
0
{}
Process finished with exit code 0
元素查询的操作:
-
Object get(Object key)
:获取指定key对应的value
-
boolean containsKey(Object key)
:是否包含指定的key
-
boolean containsValue(Object value)
:是否包含指定的value
-
int size()
:返回map中key-value对的个数
-
boolean isEmpty()
:判断当前map是否为空
-
boolean equals(Object obj)
:判断当前map和参数对象obj是否相等
测试代码
@Test
public void test4(){
Map map = new HashMap();
map.put("AA",123);
map.put(45,123);
map.put("BB",56);
// Object get(Object key)
System.out.println(map.get(45));
//containsKey(Object key)
boolean isExist = map.containsKey("BB");
System.out.println(isExist);
isExist = map.containsValue(123);
System.out.println(isExist);
map.clear();
System.out.println(map.isEmpty());
}
输出结果
123
true
true
true
Process finished with exit code 0
元视图操作的方法:
-
Set keySet()
:返回所有key构成的Set集合
-
Collection values()
:返回所有value构成的Collection集合
-
Set entrySet()
:返回所有key-value对构成的Set集合
@Test
public void test5(){
Map map = new HashMap();
map.put("AA",123);
map.put(45,1234);
map.put("BB",56);
//遍历所有的key集:keySet()
Set set = map.keySet();
Iterator iterator = set.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
System.out.println();
//遍历所有的value集:values()
Collection values = map.values();
for(Object obj : values){
System.out.println(obj);
}
System.out.println();
//遍历所有的key-value
//方式一:entrySet()
Set entrySet = map.entrySet();
Iterator iterator1 = entrySet.iterator();
while (iterator1.hasNext()){
Object obj = iterator1.next();
//entrySet集合中的元素都是entry
Map.Entry entry = (Map.Entry) obj;
System.out.println(entry.getKey() + "---->" + entry.getValue());
}
System.out.println();
//方式二:
Set keySet = map.keySet();
Iterator iterator2 = keySet.iterator();
while(iterator2.hasNext()){
Object key = iterator2.next();
Object value = map.get(key);
System.out.println(key + "=====" + value);
}
}
输出结果
AA
BB
45
123
56
1234
AA---->123
BB---->56
45---->1234
AA=====123
BB=====56
45=====1234
Process finished with exit code 0
0x06:TreeMap
TreeMap
存储 Key-Value
对时, 需要根据 key-value
对进行排序。TreeMap 可以保证所有的 Key-Value
对处于有序状态。
并且 TreeMap
底层使用红黑树结构存储数据
TreeMap 的 Key 的排序:
- 自然排序:
TreeMap
的所有的 Key 必须实现Comparable
接口,而且所有的 Key 应该是同一个类的对象,否则将会抛出ClasssCastException
- 定制排序:创建
TreeMap
时,传入一个Comparator
对象,该对象负责对TreeMap
中的所有 key 进行排序。此时不需要 Map 的 Key 实现Comparable
接口
TreeMap自然排序
//自然排序
@Test
public void test1(){
TreeMap map = new TreeMap();
User u1 = new User("Tom",23);
User u2 = new User("Jerry",32);
User u3 = new User("Jack",20);
User u4 = new User("Rose",18);
map.put(u1,98);
map.put(u2,89);
map.put(u3,76);
map.put(u4,100);
Set entrySet = map.entrySet();
Iterator iterator1 = entrySet.iterator();
while (iterator1.hasNext()){
Object obj = iterator1.next();
Map.Entry entry = (Map.Entry) obj;
System.out.println(entry.getKey() + "---->" + entry.getValue());
}
}
输出结果
User{name='Tom', age=23}---->98
User{name='Rose', age=18}---->100
User{name='Jerry', age=32}---->89
User{name='Jack', age=20}---->76
Process finished with exit code 0
TreeMap定制排序
//定制排序
@Test
public void test2(){
TreeMap map = new TreeMap(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
if(o1 instanceof User && o2 instanceof User){
User u1 = (User)o1;
User u2 = (User)o2;
return Integer.compare(u1.getAge(),u2.getAge());
}
throw new RuntimeException("输入的类型不匹配!");
}
});
User u1 = new User("Tom",23);
User u2 = new User("Jerry",32);
User u3 = new User("Jack",20);
User u4 = new User("Rose",18);
map.put(u1,98);
map.put(u2,89);
map.put(u3,76);
map.put(u4,100);
Set entrySet = map.entrySet();
Iterator iterator1 = entrySet.iterator();
while (iterator1.hasNext()){
Object obj = iterator1.next();
Map.Entry entry = (Map.Entry) obj;
System.out.println(entry.getKey() + "---->" + entry.getValue());
}
}
输出结果
User{name='Rose', age=18}---->100
User{name='Jack', age=20}---->76
User{name='Tom', age=23}---->98
User{name='Jerry', age=32}---->89
Process finished with exit code 0
TreeMap
判断两个key相等的标准:两个 key
通过compareTo()方法或者compare()方法返回0。
0x07:Hashtable
Hashtable
是个古老的 Map 实现类, JDK1.0
就提供了。不同于HashMap,Hashtable
是线程安全的。
Hashtable
实现原理和 HashMap
相同,功能相同。底层都使用哈希表结构,查询速度快,很多情况下可以互用。
- 与
HashMap
不同, Hashtable 不允许使用null
作为key
和value
- 与
HashMap
一样,Hashtable
也不能保证其中 Key-Value 对的顺序
Hashtable 判断两个 key
相等、两个 value
相等的标准, 与HashMap一致。
由于目前实际开发中 Hashtable
用得较少,所以这里就不进行详细的探究。
0x08:Properties处理配置文件
Properties 类是 Hashtable
的子类,该对象用于处理属性文件
由于属性文件里的 key
、 value
都是字符串类型,所以 Properties
里的 key
和 value
都是字符串类型
存取数据时,建议使用 setProperty(String key,String value)
方法和 getProperty(String key)
方法,如下举例
新建一个 jdbc.properties
文件,写入下面的内容
username=lcyee
password=abc123
编写测试代码
//Properties:常用来处理配置文件。key和value都是String类型
public static void main(String[] args) {
FileInputStream fis = null;
try {
Properties pros = new Properties();
fis = new FileInputStream("jdbc.properties");
pros.load(fis);//加载流对应的文件
String name = pros.getProperty("username");
String password = pros.getProperty("password");
System.out.println("username = " + name + ", password = " + password);
} catch (IOException e) {
e.printStackTrace();
} finally {
if(fis != null){
try {
fis.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
}
输出结果
username = lcyee, password = abc123
Process finished with exit code 0
0x09:Collections工具类
-
reverse(List)
:反转 List 中元素的顺序
-
shuffle(List)
:对 List 集合元素进行随机排序
-
sort(List)
:根据元素的自然顺序对指定 List 集合元素按升序排序
-
sort(List,Comparator)
:根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
-
swap(List,int, int)
:将指定 list 集合中的 i 处元素和 j 处元素进行交换
-
Object max(Collection)
: -
根据元素的自然顺序,返回给定集合中的最大元素
-
Object max(Collection,Comparator)
:根据 Comparator 指定的顺序,返回给定集合中的最大元素
-
Object min(Collection)
-
Object min(Collection,Comparator)
-
int frequency(Collection,Object)
:返回指定集合中指定元素的出现次数
-
void copy(List dest,List src)
:将src中的内容复制到dest中
-
boolean replaceAll(List list,Object oldVal,Object newVal)
:使用新值替换 List 对象的所有旧值
这里我们重点举例 copy
方法
@Test
public void test2(){
List list = new ArrayList();
list.add(123);
list.add(43);
list.add(765);
list.add(-97);
list.add(0);
//报异常:IndexOutOfBoundsException("Source does not fit in dest")
// List dest = new ArrayList();
// Collections.copy(dest,list);
//正确的:
List dest = Arrays.asList(new Object[list.size()]);
System.out.println(dest.size());//list.size();
Collections.copy(dest,list);
System.out.println(dest);
}
从上述代码可以看出,如果我们需要使用 Collections.copy()
方法对 List
进行从 A 向 B 的复制操作,需要 A 和 B 都持有对等的大小, 通过 Arrays.asList(new Object[list.size()]);
的方式,向 B
中创建于 A
对等数量的空对象,然后再进行复制操作。
同步控制
Collections 类中提供了多个 synchronizedXxx()
方法,该方法可使将指定集合包装成线程同步的集合,从而可以解决多线程并发访问集合时的线程安全问题。
//返回的list1即为线程安全的List
List list1 = Collections.synchronizedList(list);
我们从 Collections
的源码中可以看到大量的使用了 synchronized
关键字
0xFF:拓展
CurrentHashMap 与 Hashtable 的异同
为了在高并发的常见下操作Map获得更高的执行效率,所以引入了 CurrentHashMap
,其实现了分段锁的技术。
总结
- 巩固了
HashMap
的部分实现原理以及其扩容方案的实现。 - 并且了解了
HashMap
与其他的实现类例如TreeMap
、Hashtable
的一些区别。