容器基础知识
-
List:有序、不唯一
- ArrayList:Object数组
- LinkedList:双向链表(JDK1.6之前为循环链表)
- Vector:Object数组
-
Set:唯一
- HashSet:无序、唯一,底层使用HashMap实现
- LinkedHashSet:继承自HashSet,底层使用LinkedHashMap实现,而LinkedHashMap又继承自HashMap
- TreeSet:有序、唯一,红黑树(自平衡的排序二叉树)
-
Map:键值对,键唯一,值不唯一
- HashMap:数组+链表/红黑树
- LinkedHashMap:继承自HashMap,所以底层还是数组+链表/红黑树,同时还增加了一条双向链表
- HashTable:数组+链表(基本弃用)
- TreeMap:红黑树(自平衡的排序二叉树)
根据不同的场景使用不同的容器。
List
- ArrayList:线程不安全、基于数组、高效随机访问
- LinkedList:线程不安全、基于链表、节省空间
- Vector:线程安全的
ArrayList扩容每次扩大1.5倍左右,为偶数1.5被,奇数1.5倍左右。
RandomAccess接口用来标识是否具有随机访问功能,该接口没有任何方法只是用来标识,ArrayList实现了该接口。
- 实现了
RandomAccess
接口的list,优先选择普通 for 循环 ,其次 foreach, - 未实现
RandomAccess
接口的list,优先选择iterator遍历(foreach遍历底层也是通过iterator实现的),大size的数据,千万不要使用普通for循环
HashMap
HashMap是非线程安全的,如果需要线程安全就使用ConcurrentHashMap,因为HashTable基本被淘汰。
HashMap中:
- null可以作为键。
- 默认初始大小为16
- 扩容一次扩大2倍
- 初始时,key对应的是一个链表
- JDK1.8后,为解决哈希冲突,当链表长度大于8时,就转换为红黑树
哈希冲突:因为key是任意的,所以key哈希后可能会产生相同的哈希值。
JDK1.8之前,使用链表+数组解决哈希冲突。
JDK1.8后
HashMap与HashSet的区别
其实HashSet的底层是基于HashMap实现的
HashMap | HashSet |
---|---|
实现Map接口 | 实现了Set接口 |
添加元素用put()方法 | 添加元素用add()方法 |
使用key计算HashCode值 | 使用对象计算HashCode值 |
因为HashSet是唯一的,所以需要检查对象是否重复,使用对象来计算HashCode的值,而有可能会产生相同的哈希值,当产生相同的哈希值时就需要调用equals方法判断是否为同一个对象。
hashCode()与equals()的规定:
hashCode()方法的默认情况下是根据内存地址来计算哈希值,也就是说任意两个对象的哈希值一定是不同的,尽管两个对象的数据内容是一样的。
- 两个对象相等,则hashcode值必须相等
- 两个对象相等,equals方法必须返回true
- 两个对象hashcode值相等,但是两个对象不一定相等
综上三个规定,可以知道,如果覆盖了equals方法(判断对象的数据内容是否一样),则必须覆盖hashCode()方法。因为Set是唯一的,而hashCode()方法的默认实现是不可能产生重复的哈希值的,这样就会导致Set添加了数据内容相同的对象。
HashMap 的长度为什么是2的幂次方
为了方便将哈希值映射为数组下标。
Hash 值的范围值-2147483648到2147483647,前后加起来大概40亿的映射空间,这么大的长度数组内存是放不下的,所以必须使用一定的规则来计算下标,最简单的就是使用%运算符hash%length,当数组长度为2的幂次方时hash%length==hash&(length-1),并且&运算的效率比%高,所以使用2幂次方能够提高下标的计算效率。
ConcurrentHashMap 和 Hashtable 的区别
- ConcurrentHashMap:底层采用数组+链表/红黑树、使用分段锁提高并发效率
- Hashtable :底层采用数组+链表,使用全表锁