目录
HashMap集合的底层原理
LinkHashMap的底层原理
TreeMap的底层原理
HashMap集合的底层原理
HashMap的特点
- HashMap(由键决定特点):无序、不重复、无索引;(用的最多)
HashMap的底层原理
- HashMap跟HashSet的底层原理是一模一样的,都是基于哈希表实现的。
实际上:原来学的Set系列集合的底层就是基于Map实现的,只是Set集合中的元素只要键数据,不要值数据而已。
public HashSet(){
map = new HashMap<>();
}
哈希表
- JDK8之前,哈希表 = 数组 + 链表
- JDK8开始,哈希表 = 数组 + 链表 + 红黑树
- 哈希表是一种增删改查数据,性能都较好的数据结构。
HashMap底层是基于哈希表实现的
- HashMap集合是一种增删改查数据,性能都较好的集合
- 但是它是无序,不能重复,没有索引支持的(由键决定特点)
- HashMap的键依赖hashCode方法和equals方法保证键的唯一
- 如果键存储的是自定义类型的对象,可以通过重写hashCode和equals方法,这样可以保证多个对象内容一样时,HashMap集合就能认为是重复的。
LinkHashMap的底层原理
LinkHashMap的特点
- LinkedHashMap(由键决定特点):有序、不重复、无索引。
LinkHashMap的底层原理
- 底层数据结构依然是基于哈希表实现的,只是每个键值对元素又额外的多了一个双链表的机制记录元素顺序(保证有序)。
实际上:原来学习的LinkedHashSet集合的底层原理就是LinkedHashMap。
详细看一遍哈希表+双链表的存储过程:
1.插入第一个元素,计算哈希值存储对应位置,此时头尾指针为同一个
2.插入第二个元素,移动尾指针,同时与第一个元素进行双向链接
3. 插入第三个元素,假设此时计算的哈希值与第二个元素重复,则链接为链表,即接在第二个元素下面,移动尾指针,同时与第二个元素进行双向链接
4.插入第四个元素,与插入第二元素的过程一样
在Map中,这些元素都代表着一个个Entry对象
TreeMap的底层原理
- 特点:不重复、无索引、可排序 (按照键的大小默认升序排序,只能对键排序)
- 原理:TreeMap跟TreeSet集合的底层原理是一样的,都是基于红黑树实现的排序。
TreeMap集合同样也支持两种方式来指定排序规则
- 让类实现comparable接口,重写比较规则。
- TreeMap集合有一个有参数构造器,支持创建Comparator比较器对象,以便用来指定比较规则。
END
学习自:黑马程序员——JavaSE课程