1.首先我们常用的Map和List是出于两个分支,List和Set是Collection的子接口,而Map则是与Collection同级别的.
2.HashSet的底层是HashMap,所以我们理解HashMap的扩容机制即可.
- 添加一个元素时,先得到hash值-会转成-->索引值
- 找到存储数据表table,到这个索引位置是否已经存放有元素,如果没有直接加入
- 如果有,调用equals比较,如果相同,就放弃添加,如果不相同,则添加到最后
- 如果一条链表的元素个数达到8,并且table的大小达到64,就会进行树化
3.List下面的集合类一般都是允许录入重复值的,而Set的集合类确是不允许出现重复值的
4.List和Set的实现集合都是单列集合,而Map的实现集合都是双列集合.
下表整理出了各个集合之间的特点:
| Collection | Map | |||
| 无序 不唯一 | Collection | Map.value() | ||
| 有序 不唯一 | ArrayList | linkedList | ||
| 无序 唯一 | HashSet | HashMap KeySet | ||
| 有序 唯一 | linkedHashSet | TreeSet | linkedHashMap KeySet | TreeMap KeySet |
| 存储结构 | 输出顺序 | 唯一性 | 查询效率 | 添加/删除效率 | |
| ArrayList | 顺序表 | 有序(添加) | 不唯一 | 索引查询效率最高 | 效率低 |
| linkedList | 双向链表 | 有序(添加) | 不唯一 | 效率低 | 效率高 |
| HashSet | Hash表 | 无序 | 唯一 | 效率最高 | 效率最高 |
| HashMap | Hash表 | Key无序 | key唯一 | 效率最高 | 效率最高 |
| linkedHashSet | Hash表+链表 | 有序(添加) | 唯一 | 效率最高 | 效率最高 |
| linkedHashMap | Hash表+链表 | Key有序(添加) | key唯一 | 效率最高 | 效率最高 |
| TreeSet | 红黑树 | 有序(自然) | 唯一 | 效率中等 | 效率中等 |
| TreeMap | 红黑树 | 有序(自然) | key唯一 | 效率中等 | 效率中等 |
