免责声明:
1.2 常见集合
List,Set,Map 的区别以及选用
List 和 Set 都继承与 Collection 接口;
List:1. 可以允许重复的对象.
2. 可以插入多个 null 元素.
3. 是一个有序容器, 保持了每个元素的插入顺序, 输出的顺序就是插入的顺序.
4. 常用的实现类有 ArrayList,LinkedList 和 Vector.ArrayList 最为流行, 它提供了使用索引的随意访问, 而 LinkedList 则对于经常需要从 List 中添加或删除元素的场合更为合适.
Set:1. 不允许重复对象
2. 无序容器, 你无法保证每个元素的存储顺序, TreeSet 通过 Comparator 或者 Comparable 维护了一个排序顺序.
3. 只允许一个 null 元素
4.Set 接口最流行的几个实现类是 HashSet,LinkedHashSet 以及 TreeSet. 最流行的是基于 HashMap 实现的 HashSet;TreeSet 还实现了 SortedSet 接口, 因此 TreeSet 是一个根据其 compare() 和
compareTo() 的定义进行排序的有序容器.
Map:
1.Map 不是 collection 的子接口或者实现类. Map 是一个接口.
2.Map 的 每个 Entry 都持有两个对象, 也就是一个键一个值, Map 可能会持有相同的值对象但键对象必须是唯一的.
TreeMap 也通过 Comparator 或者 Comparable 维护了一个排序顺序.
Map 里你可以拥有随意个 null 值但最多只能有一个 null 键.
5.Map 接口最流行的几个实现类是 HashMap,LinkedHashMap,Hashtable 和 TreeMap.(HashMap,TreeMap 最常用)
Set 和 hashCode 以及 equals 方法的联系
**
set 保证里面元素的唯一性其实是靠两个方法, 一是 equals()和 hashCode()方法;
set 在存入数据使用了 hashCode(), 先进行取 hashcode, 在将得到的值插入到指定算出来的地址上, 如果下次有相同值对应这个地址, 则使用 equals()比较, 相同则过滤, 不同则通过解决冲突算法, 将该值存入起来.
Arraylist 与 LinkedList 区别
**
LinkedeList 和 ArrayList 都实现了 List 接口, 但是它们的工作原理却不一样. ArrayList 是实现了基于动态数组的数据结构, LinkedList 基于链表的数据结构. (LinkedList 是双向链表, 有 next 也有 previous)
区别:
1) 因为 Array 是基于索引 (index) 的数据结构, 它使用索引在数组中搜索和读取数据是很快的. Array 获取数据的时间复杂度是 O(1), 但是要删除数据却是开销很大的, 因为这需要重排数组中的所有数据.
2) 相对于 ArrayList,LinkedList 插入是更快的. 因为 LinkedList 不像 ArrayList 一样, 不需要改变数组的大小, 也不需要在数组装满的时候要将所有的数据重新装入一个新的数组, 这是 ArrayList 最坏的一种情况, 时间复杂度是 O(n), 而 LinkedList 中插入或删除的时间复杂度仅为 O(1).ArrayList 在插入数据时还需要更新索引(除了插入数组的尾部).
3) 类似于插入数据, 删除数据时, LinkedList 也优于 ArrayList.
ArrayList 与 Vector 区别
首先看这两类都实现 List 接口, 而 List 接口一共有三个实现类, 分别是 ArrayList,Vector 和 LinkedList.List 用于存放多个元素, 能够维护元素的次序, 并且允许元素的重复. 相关区别如下:
1,Vector 与 ArrayList 一样, 都是通过数组实现的, 不同的是它支持线程的同步, 即某一时刻只有一个线程能够写 Vector, 避免多线程同时写而引起的不一致性, 但实现同步需要很高的花费, 因此, 访问它比访问 ArrayList 慢.
2,ArrayList 在内存不够时默认是扩展 50% + 1 个, Vector 是默认扩展 1 倍.
HashMap,ConcurrentHashMap,HashTable 的区别
引入 ConcurrentHashMap 是为了在同步集合 HashTable 之间有更好的选择, HashTable 与 HashMap,ConcurrentHashMap 主要的区别在于 HashMap 不是同步的, 线程不安全的和不适合应用于多线程并发环境下, 而 ConcurrentHashMap 是线程安全的集合容器, 特别是在多线程和并发环境中, 通常作为 Map 的主要实现.
1, 第一个重要的区别就是 ConcurrentHashMap 是线程安全的和在并发环境下不需要加额外的同步. 虽然它不像 Hashtable 那样需要同样的同步等级(全表锁), 但也有很多实际的用途.
2, 你可以使用 Collections.synchronizedMap(HashMap)来包装 HashMap 作为同步容器, 这时它的作用几乎与 Hashtable 一样, 当每次对 Map 做修改操作的时候都会锁住这个 Map 对象, 而 ConcurrentHashMap 会基于并发的等级来划分整个 Map 来达到线程安全, 它只会锁操作的那一段数据而不是整个 Map 都上锁.
3,ConcurrentHashMap 有很好的扩展性, 在多线程环境下性能方面比做了同步的 HashMap 要好, 但是在单线程环境下, HashMap 会比 ConcurrentHashMap 好一点.
总结一下以上两者的区别, 它们在线程安全, 扩展性, 同步之间的区别. 如果是用于缓存的话, ConcurrentHashMap 是一个更好的选择, 在 Java 应用中会经常用到.
4,Hashtable 是 jdk1 的一个遗弃的类, 它把所有方法都加上 synchronized 关键字来实现线程安全. 所有的方法都同步这样造成多个线程访问效率特别低. Synchronized Map 与 HashTable 差别不大, 也是在并发中作类似的操作, 两者的唯一区别就是 Synchronized Map 没被遗弃, 它可以通过使用 Collections.synchronizedMap()来包装 Map 作为同步容器使用.
HashMap 的工作原理及代码实现, 什么时候用到红黑树
HashMap 工作原理及什么时候用到的红黑树:
在 jdk 1.7 中, HashMap 采用位桶 + 链表实现, 即使用链表处理冲突, 同一 hash 值的链表都存储在一个链表里. 但是当位于一个桶中的元素较多, 即 hash 值相等的元素较多时, 通过 key 值依次查找的效率较低.
在 jdk 1.8 中, HashMap 采用位桶 + 链表 + 红黑树实现, 当链表长度超过阈值 (8) 时, 将链表转换为红黑树, 这样大大减少了查找时间.
原理:
数组中的每一个元素所在的位置相当于一个位桶, 添加元素的时候, 首先计算元素 key 的 hash 值, 确定插入数组中的位置 (也就是哪个桶中), 如果存在相同的 hash 值, 则放在同一个桶中(元素位置) 形成链表, 当链表长度超过阈值 (8) 时, 将链表转换为红黑树;
内部结构:
1,HashMap 底层是基于数组和链表实现的, 如图所示, 其中两个重要的参数: 容量和负载因子; 容量的默认大小是 16, 负载因子是 0.75, 当? HashMap? 的? size> 16*0.75? 时就会发生扩容(容量和负载因子都可以自由调整).
2, 内部包含了一个 Node 类型的数组 table(Entry<K,V>[] table 为 jdk 1.7 中).
3,Node 存储着键值对. 它包含了四个字段, 从 next 字段我们可以看出 Node 是一个链表. 即数组中的每个位置被当成一个桶, 一个桶存放一个链表. HashMap 使用拉链法来解决冲突, 同一个链表中存放哈希值相同的 Node;
拉链法的工作原理(解决 hash 冲突):
新建一个 HashMap, 默认大小为 16;
插入 <K1,V1> 键值对, 先计算 K1 的 hashCode 为 115, 使用除留余数法得到所在的桶下标 115%16=3.
插入 <K2,V2> 键值对, 先计算 K2 的 hashCode 为 118, 使用除留余数法得到所在的桶下标 118%16=6.
插入 <K3,V3> 键值对, 先计算 K3 的 hashCode 为 118, 使用除留余数法得到所在的桶下标 118%16=6, 插在 <K2,V2> 前面.
应该注意到链表的插入是以头插法方式进行的, 例如上面的 <K3,V3> 不是插在 <K2,V2> 后面, 而是插入在链表头部;
查找需要分成两步进行:
1, 计算键值对所在的桶;
2, 在链表上顺序查找, 时间复杂度显然和链表的长度成正比;
HashMap 允许插入键为 null 的键值对. 但是因为无法调用 null 的 hashCode() 方法, 也就无法确定该键值对的桶下标, 只能通过强制指定一个桶下标来存放. HashMap 使用第 0 个桶存放键为 null 的键值对.
多线程情况下 HashMap 死循环的问题
如果扩容前相邻的两个 Entry 在扩容后还是分配到相同的 table 位置上, 就会出现死循环的 BUG. 在复杂的生产环境中, 这种情况尽管不常见, 但是可能会碰到.
HashMap 出现 Hash DOS 攻击的问题
ConcurrentHashMap 的工作原理及代码实现, 如何统计所有的元素个数
看过那些 Java 集合类的源码
手写简单的 HashMap
来源: http://www.bubuko.com/infodetail-2990757.html