29. Map接口继承关系 / Map接口概述 / HashMap底层实现原理及相关知识 / Map常用方法 / TreeMap、Properties

Map接口继承关系

Map接口概述

• Map与Collection并列存在。用于保存具有映射关系的数据:key-value
• Map 中的 key 和 value 都可以是任何引用类型的数据
• Map 中的 key 用Set来存放， 不允许重复，即同一个 Map 对象所对应
  的类，须重写hashCode()和equals()方法
• 常用String类作为Map的“键”
• key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到
  唯一的、确定的 value
• Map接口的常用实现类： HashMap、 TreeMap、 LinkedHashMap和
  Properties。 其中， HashMap是 Map 接口使用频率最高的实现类

• /----Map:双列数据，存储key-value
• • /----HashMap:线程不安全，效率高；可存储null的key和value
    底层实现 JDK7：数组+链表
    JDK8：数组+链表+红黑树
• • • /----LinkedHashMap:可保证遍历map元素时按照添加顺序遍历；因为在原有hashmap的基础上加了一对指针保存之前和之后的数据。对于频繁遍历比较高效。
• • /----TreeMap:保证添加的key-value键值对是有序的，按key进行自然或定制排序。
    底层实现 红黑树
• • /----Hashtable:线程安全，效率低；不可存储null的key和value
• • • /----Properties:长用来处理配置文件，key和value都是String类型

Map中的key-value的理解：

• key是无序不可重复的，用set来存；–>key所在的类要重写equals和hashcode方法
• value可以重复，Collection存；–>value所在的类要重写equals
• 实际上map中放的是Entry对象，Entry对象中有两个属性，也就是key和value
  Map中的entry是无序不可重复的，用Set来存

HashMap底层实现原理？

HashMap底层实现原理？
JDK7
底层使用数组+链表。
HashMap map = new HashMap();实例化之后
1.底层创建了长度为16的一维数组Entry[] table;
map.put(key1,value1):
1.首先调用key1所在类的hashcode方法，
2.计算key1对应的哈希值，根据算法计算其在Entry数组中的存放位置

• 若该位置上无数据，则key1-value1添加成功；
• 若该位置上有数据，（则此位置上存在一个或多个数据，多个数据以链表形式存在）,比较key1和已经存在的一个或多个数据的hash值：
• • 若key1的hash值尚未出现过，则key1-value1添加成功
• • 若key1的hash值与存在的某数据(key2-value2)相同，继续比较：调用key1所在类的equals(key2)方法：
• • • 若equals()==true：使用value1替换value2. 也就是说put()有更新修改的作用
• • • 若equals()==false，则key1-value1添加成功

扩容：存放数据过程中，当数据元素数量超过临界值（且要存放的位置已有元素存在）时，数组扩容为原来的2倍，并将原有数据复制过去。{计算临界值的方法：数组长度*装填因子（一般设置为0.75）}
将原有数据复制到新的数组空间时，需要重新计算原有数据的hash值及其在新数组的索引位置，这一过程很耗时

JDK8
与JDK7的区别：数组+链表+红黑树
HashMap map = new HashMap();实例化之后，并不会创建一个长度为16的数组；其底层数组为Node[]
首次调用put方法时，底层创建长度为16的数组；
当数组的某个索引位置上的元素以链表形式存在的数据个数>8,且当前数组长度>64,
则此时索引位置上的所有数据改为使用红黑树存储。
（其余过程相同）

HashMap源码中的重要常量

Map常用方法

TreeMap

Properties

该博客图片来源于尚硅谷宋老师教学课件