集合

常见的集合有哪些

Java集合类主要由两个接口Collection和Map派生出来。 Collection有三个子接口 List，Set，Queue Map List代表了有序可重复集合，可以根据元素的索引来访问；Set表示无序不重复集合，只能根据元素本身来访问；Queue是队列集合。 Map代表是存储Key-Value集合，可以根据元素key来访问value

List，Set和Map的区别

List以索引来存取元素，有序的，元素是允许重复的，可插入多个null； Set不能存放重复元素，无序的，只允许一个null Map保存键值对映射 List底层实现有数组，链表两种方式；Set，Map容器有基于哈希存储和红黑树两种方式实现； Set基于Map实现，Set里的元素值就是Map的键值

ArrayList了解吗

ArrayList底层是动态数组，它的容量能动态增长，在添加大量元素前，应用可以使用ensureCapacity操作增加ArrayList实例的容量。ArrayList继承了AbstractList，并实现了List接口。

ArrayList的扩容机制

ArrayList扩容的本质就是计算出新的扩容数组的size后实例化，并将原有数组内容复制到新数组中去。默认情况下，新的容量会是原来的1.5倍。

怎么在遍历ArrayList时移除一个元素

foreach删除会导致快速失败问题，可以使用迭代器的remove()方法

ArrayList和Vector区别

1.ArrayList在内存不够时，扩容为原来的1.5倍，Vector是扩容为原来的2倍 2.Vector属于线程安全级别的，但是大多数情况下不使用Vector，因为操作Vector效率比较低

ArrayList和LinkedList区别

1.ArrayList基于动态数组实现；LinkedList基于链表实现 2.对于随机index访问的get和set方法，ArrayList速度要优于LinkedList。因为ArrayList直接通过数组下标直接找到元素；LinkedList要移动指针遍历每个元素为止 3.新增和删除元素，LinkedList速度要优于ArrayList。因为ArrayList在新增和删除元素时，可能扩容和复制数组；LinkedList实例化对象需要时间外，只需要修改指针即可。

HashMap

HashMap使用数组+链表+红黑树（JDK8增加了红黑树部分）实现的，链表长度大于8时，会把链表转换为红黑树，红黑树节点个数小于6时才转换成链表，防止频繁的转化

解决Hash冲突的方法有哪些？HashMap用的哪种

开放地址法： 如果p=H(key)出现冲突时，则以p为基础，再次hash，p1=H(p)，如果p1再次出现冲突，则以p1为基础，以此类推，直到找到一个不冲突的哈希地址pi。因此开放地址法需要的hash表的长度要大于等于所需要存放的元素，而且因为存在再次hash，所以只能在删除上做标记，不能真正删除节点。 再哈希法： 提供多个不同的hash函数，当R1=H1(key1)发生冲突时，再计算R2=H2(key1)，直到没有冲突为止。这样做虽然不易产生堆积，但增加了计算的时间 链地址法： 将哈希值相同的元素构成一个同义词的单链表，并将单链表的头指针存放再哈希表的第i个单元中，查找，插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况

使用hash算法

Hash算法：取key的hashCode值，高位运算，取模运算。

h=key.hashCode()//第一步，取hashCode值
h ^ (h >>> 16)//第二步 高位参与运算，减少冲突
return h & (length - 1)

高16位异或低16位：这么做可以在数组比较小的时候，也能保证考虑到高低位都参与到Hash的计算中，可以减少冲突，同时不会有太大的开销。