Java集合面试题专题该为北京面试面试题记录不喜勿喷什么是hash碰撞如果两个元素不相同,但是hash函数的值相同,这两个元素就是一个碰撞因为把任意长度的字符串变成固定长度的字符串,所以存在一个hash对应多个字符串的情况,所以碰撞必然存在hashMap默认容量为什么是16- 默认容量都是 16 负载因子是 0.75 。就是当 HashMap 填充了 75% 的 busket 是就会扩容最小的可能性是16 * 0.75 12为了减少hash值的碰撞,需要实现一个尽量均匀分布的hash函数,在HashMap中通过利用key的hashcode值,来进行位运算公式:index e.hash (newCap - 1)反观长度16或者其他2的幂,length - 1的值是所有二进制位全为1,这种情况下,index的结果等同于hashcode后几位的值 只要输入的hashcode本身分布均匀,hash算法的结果就是均匀的所以,**HashMap的默认长度为16,是为了降低hash碰撞的几率参考文章HashMap 的长度为什么是 2 的幂次方为了能让 HashMap 存取高效尽量较少碰撞也就是要尽量把数据分配均匀每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。参考地址HashMap实现原理·Java 中最常用的两种结构是数组和模拟指针引用几乎所有的数据结构都可以利用这两种来组合实现HashMap 也是如此。实际上 HashMap 是一个“链表散列”。HashMap 是基于 hashing 的原理。HashMap由数组链表组成的数组是HashMap的主体链表则是主要为了解决哈希冲突而存在的如果定位到的数组位置不含链表当前entry的next指向null,那么对于查找添加等操作很快仅需一次寻址即可参考文章·我们使用 #put(key, value) 方法来存储对象到 HashMap 中使用 get(key) 方法从 HashMap 中获取对象。 当我们给 #put(key, value) 方法传递键和值时我们先对键调用 #hashCode() 方法返回的 hashCode 用于找到 bucket 位置来储存 Entry 对象。多线程调用HashMap导致的问题主要是多线程同时put时如果同时触发了rehash操作会导致HashMap中的链表中出现循环节点进而使得后面get的时候会死循环cup飙升至100%文章与HashTable的区别HashTable和HashMap的实现原理几乎一样差别无非是1.HashTable不允许key和value为null2.HashTable是线程安全的。但是HashTable线程安全的策略实现代价却太大了简单粗暴get/put所有相关操作都是synchronized的这相当于给整个哈希表加了一把大锁多线程访问时候只要有一个线程访问或操作该对象那其他线程只能阻塞相当于将所有的操作串行化在竞争激烈的并发场景中性能就会非常差。ConcurrentHashMap实现原理ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁ReentrantLock在ConcurrentHashMap里扮演锁的角色HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组Segment的结构和HashMap类似是一种数组和链表结构 一个Segment里包含一个HashEntry数组每个HashEntry是一个链表结构的元素 每个Segment守护者一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时必须首先获得它对应的Segment锁。扩容扩容的时候首先会创建一个两倍于原容量的数组然后将原数组里的元素进行再hash后插入到新的数组里。为了高效ConcurrentHashMap不会对整个容器进行扩容而只对某个segment进行扩容。ConcurrentHashMap的锁分段技术首先将数据分成一段一段的存储然后给每一段数据配一把锁当一个线程占用锁访问其中一个段数据的时候其他段的数据也能被其他线程访问。有些方法需要跨段比如size()和containsValue()它们可能需要锁定整个表而而不仅仅是某个段这需要按顺序锁定所有段操作完毕后又按顺序释放所有段的锁。这里“按顺序”是很重要的否则极有可能出现死锁在ConcurrentHashMap内部段数组是final的并且其成员变量实际上也是final的但是仅仅是将数组声明为final的并不保证数组成员也是final的这需要实现上的保证。这可以确保不会出现死锁因为获得锁的顺序是固定的。参考ConcurrentHashMap的读是否要加锁为什么不加锁在1.8中ConcurrentHashMap的get操作全程不需要加锁这也是它比其他并发集合比如hashtable、用Collections.synchronizedMap()包装的hashmap;安全效率高的原因之一。 get操作全程不需要加锁是因为Node的成员val是用volatile修饰的和数组用volatile修饰没有关系。 数组用volatile修饰主要是保证在数组扩容的时候保证可见性。参考文章ConcurrentHashMap的迭代器是强一致性的迭代器还是弱一致性的迭代器弱一致性在这种迭代方式中当iterator被创建后集合再发生改变就不再是抛出ConcurrentModificationException取而代之的是在改变时new新的数据从而不影响原有的数据iterator完成后再将头指针替换为新的数据这样iterator线程可以使用原来老的数据而写线程也可以并发的完成改变更重要的这保证了多个线程并发执行的连续性和扩展性是性能提升的关键。HashMap 和 ConcurrentHashMap 的区别oncurrentHashMap 是线程安全的 HashMap 的实现;1、ConcurrentHashMap 对整个桶数组进行了分割分段(Segment)然后在每一个分段上都用 lock 锁进行保护相对 于Hashtable 的 syn 关键字锁的粒度更精细了一些并发性能更好。而 HashMap 没有锁机制不是线程安全的。JDK8 之后ConcurrentHashMap 启用了一种全新的方式实现,利用 CAS 算法。2、HashMap 的键值对允许有 null 但是 ConCurrentHashMap 都不允许。HashSet实现原理HashSet中不允许有重复元素这是因为HashSet是基于HashMap实现的HashSet中的元素都存放在HashMap的key上面而value中的值都是统一的一个private static final Object PRESENT new Object();。HashSet跟HashMap一样都是一个存放链表的数组。整理 1HashSet底层由HashMap实现 2HashSet的值存放于HashMap的key上 3HashMap的value统一为PRESENTHashSet 和 TreeSet 的区别1、 TreeSet 是二差树实现的,Treeset中的数据是自动排好序的不允许放入null值。 2、HashSet 是哈希表实现的,HashSet中的数据是无序的可以放入null但只能放入一个null两者中的值都不能重复就如数据库中唯一约束。 3、HashSet要求放入的对象必须实现HashCode()方法放入的对象是以hashcode码作为标识的而具有相同内容的 String对象 hashcode是一样所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例 。如何选用对于在 Map 中插入、删除和定位元素这类操作HashMap 是最好的选择。 然而假如你需要对一个有序的 key 集合进行遍历 TreeMap 是更好的选择。ArrayList 与 LinkedList 区别ArrayList 是实现了基于动态数组的数据结构因为地址连续一旦数据存储好了查询操作效率会比较高在内存里是连着放的。因为地址连续ArrayList 要移动数据所以插入和删除操作效率比较低。LinkedList 基于链表的数据结构地址是任意的所以在开辟内存空间的时候不需要等一个连续的地址。对于新增和删除操作 add 和 remove LinedList 比较占优势。LinkedList 适用于要头尾操作或插入指定位置的场景。因为 LinkedList 要移动指针所以查询操作性能比较低。选用场景当需要对数据进行对随机访问的情况下选用 ArrayList 。当需要对数据进行多次增加删除修改时采用 LinkedList 。如果容量固定并且只会添加到尾部不会引起扩容优先采用 ArrayList 。ArrayList 扩容如果通过无参构造的话初始数组容量为0当真正对数组进行添加时才真正分配容量。每次按照1.5倍位运算的比率通过copeOf的方式扩容。 在JKD1.6中实现是如果通过无参构造的话初始数组容量为10.每次通过copeOf的方式扩容后容量为原来的1.5倍加1.以上就是动态扩容的原理。参考ArrayList 与 Vector 区别ArrayList 和 Vector 都是用数组实现的;区别1、Vector 是多线程安全的线程安全就是说多线程访问同一代码不会产生不确定的结果而 ArrayList 不是。Vector 类中的方法很多有 synchronized 进行修饰这样就导致了 Vector 在效率上无法与 ArrayList 相比。2、两个都是采用的线性连续空间存储元素但是当空间不足的时候两个类的增加方式是不同。3、Vector 可以设置增长因子而 ArrayList 不可以。适用场景分析1、Vector 是线程同步的所以它也是线程安全的而 ArrayList 是线程无需同步的是不安全的。如果不考虑到线程的安全因素一般用 ArrayList 效率比较高。实际场景下如果需要多线程访问安全的数组使用 CopyOnWriteArrayList 。2、如果集合中的元素的数目大于目前集合数组的长度时在集合中使用数据量比较大的数据用 Vector 有一定的优势。这种情况下使用 LinkedList 更合适。