Java中的集合，从ArrayList一直讲到ConcurrentHashMap，其中包括底层数据结构，扩容，并发问题。

HashMap是不是线程安全的，ConcurrentHashMap怎么实现线程安全

Collection

1. Set

  • TreeSet：基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如 HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。

  • HashSet：基于哈希表实现，支持快速查找，但不支持有序性操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。

  • LinkedHashSet：具有 HashSet 的查找效率，且内部使用双向链表维护元素的插入顺序。

2. List

  • ArrayList：基于动态数组实现，支持随机访问。

  • Vector：和 ArrayList 类似，但它是线程安全的。

  • LinkedList：基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。

3. Queue

  • LinkedList：可以用它来实现双向队列。

  • PriorityQueue：基于堆结构实现，可以用它来实现优先队列。

 

 

 

Map

  • TreeMap：基于红黑树实现。

  • HashMap：基于哈希表实现，线程不安全。

  • HashTable：和 HashMap 类似，但它是线程安全的，这意味着同一时刻多个线程可以同时写入 HashTable 并且不会导致数据不一致。它是遗留类，不应该去使用它。现在可以使用 ConcurrentHashMap 来支持线程安全，并且 ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。

  • LinkedHashMap：使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用（LRU）顺序。

 

 

ArrayList实现了RandomAccess接口，支持随机访问; 基于数组实现的，默认大小为10；

扩容时，每次扩充旧容量的1.5倍：oldCapacity + (oldCapacity >> 1)。 

 

HashMap（常考常问）

hash：将任意长度的二进制值通过映射关系（哈希算法）转换为固定长度的二进制值；value值映射为了固定长度的key

输入key，通过hash算法，找到数组中这个value的下标，从而找到value；

hashMap找值的时间复杂度为O(1)

hash函数

%        5%2=1   等

 

hash表处理冲突的形式：

1.线性探测法：有人占了就往后面找，探测步长为1

2.链表形式 

Hash值重复了就会以链表形式存储

 

一些Hashmap的面试题：

【Hashmap和Hashtable的比较】

  • HashTable 使用 synchronized 来进行同步，线程安全。
  • HashMap 可以插入键为 null 的 Entry。
  • HashMap 的迭代器是 fail-fast 迭代器。

    所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。
  • HashMap 不能保证随着时间的推移 Map 中的元素次序是不变的。

ConcurrentHashMap是java5之后Hashtable的替代品，比Hashtable的替代性更好

ConcurrentHashMap 和 HashMap 实现上类似，最主要的差别是 ConcurrentHashMap 采用了分段锁（Segment），每个分段锁维护着几个桶（HashEntry），多个线程可以同时访问不同分段锁上的桶，从而使其并发度更高（并发度就是 Segment 的个数）。

 

【HashMap的内部实现】
HashMap的底层是用hash数组和单向链表实现的 ，当调用put方法是，首先计算key的hashcode，定位到合适的数组索引，然后再在该索引上的单向链表进行循环遍历用equals比较key是否存在，如果存在则用新的value覆盖原值，如果没有则插入单向链表的头部。HashMap的两个重要属性是容量capacity和加载因子loadfactor，默认值分布为16和0.75，当容器中的元素个数大于 capacity*loadfactor时，容器会进行扩容resize 为2n，在初始化Hashmap时可以对着两个值进行修改，负载因子0.75被证明为是性能比较好的取值，通常不会修改，那么只有初始容量capacity会导致频繁的扩容行为，这是非常耗费资源的操作，所以，如果事先能估算出容器所要存储的元素数量，最好在初始化时修改默认容量capacity，以防止频繁的resize操作影响性能。

 

【HashMap的容量为什么是2的n次幂？】
HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法； 这个算法实际就是取模，hash%length，计算机中直接求余效率不如位移运算，源码中做了优化hash&(length-1)， hash%length==hash&(length-1)的前提是length是2的n次方； 为什么这样能均匀分布减少碰撞呢？2的n次方实际就是1后面n个0，2的n次方-1  实际就是n个1； 例如长度为9时候，3&(9-1)=0  2&(9-1)=0 ，都在0上，碰撞了； 例如长度为8时候，3&(8-1)=3  2&(8-1)=2 ，不同位置上，不碰撞； 其实就是按位“与”的时候，每一位都能  &1  ，也就是和1111……1111111进行与运算