ArrayList
HashMap
1）HashMap是map的一个实现类，其key不允许重复，key可以为null，value任意，包括null。
2）在java8之前，HashMap是由数组和链表来实现的，用’拉链法’解决冲突。其中数组的默认长度为16，即HashMap的默认容量，最大长度（容量）为2的30次方。Java8后，长度超过8的链表将转存为红黑树，小于8的链表存为链表形势
3）HashMap中默认的负载因子为0.75，当元素个数大于容量乘以负载因子时，表明数组应该扩容而不是继续加入元素。扩容后的容量为size=oldSize*2。
4）HashMap不是线程安全的，表现为在JDK1.8之前，并发情况下put导致resize时，会产生循环，当再次执行到循环位置时，就会触发死循环。JDK1.8中，通过增加head和tail，优化了这个死循环问题。因为resize时头插法移动链表时的顺序是反过来的，原来链表中的顺序是1->2->3，那么移动后的顺序是3->2->1，1和2之间在并发情况下就有可能产生死锁。
为什么默认长度是16（或者2的幂次方）？
数组的长度总是为2的幂次方，之所以设置默认长度为16，是因为在key进行hash找位置过程中，需要根据key的hash值，同数组长度length-1进行与运算，然后得到几就存在放第几个桶中,length为16是，其length-1的二进制是1111，与key的hash值进行与运算后的结果，等于hash值的后四位，length不影响分布概率，完全取决于hash算法，可以得到0到15的每一个值，即可以落到第0个到底15个桶之间的每一个桶，如果默认容量采用非2的幂次方，例如10，那么其length-1的二进制是1001，进行与运算后，多种hash值最后都得到1001，且永远得不到一些值，例如0111，严重影响了均匀分布。
JDK1.8之前的HashMap死循环如何产生？
参考：https://www.cnblogs.com/xrq730/p/5037299.html
首先导致产生循环的代码是resize中的transfer方法，关键代码如下：
| 1 Entry 5 e = next; |
|---|
JDK1.7中transfer采用的是遍历原链表，然后头插法，假设原来的三个节点在扩容重新hash后仍然落在同一个下标，这样的话，原来链表中的顺序是1->2->3，那么移动后的顺序是3->2->1。并发插入时，假设线程A刚执行完第一行Entry
总结来说，JDK1.8之前transfer采用的是头插法，头插法会导致链表中上的节点在经过transfer后倒序，在并发插入时，有可能形成环，再次执行到环的位置时，就会触发死循环。JDK1.8后虽然优化解决了此问题，但仍然有数据丢失问题，所以并发环境下建议使用ConcurrentHashMap来代码HashMap。
HashMap精讲文章
https://juejin.im/post/5e843ca151882573672209c1
hashcode和equals
为什么重写equals的时候，一定要重写hashcode？
答：比较两个对象是否相等时，首先会比较两个对象的hashcode，然后比较两个对象是否满足equals，只有两者都满足是才认为相等。而Object中的hashcode计算，是依据对象地址计算的，两个实例对象其对应的堆地址肯定是不同的，那其比较时也就必然是不同的。但是对于一些我们自定义的对象，比如Student、User，我们一般会重写其equals方法，此时如果不重写其hashcode方法，那么new User(“LiMing”)与new User(“LiMing”)就会是不相等的，进而会影响到User在HashSet和HashMap中的使用。
HashTable
1）HashTable的底层也是数组+链表组成的。其key和value均不允许为空。通过对整张hash使用synchronized，同一时刻只允许一个线程可以操作HashTable，来达到线程安全的目的，但是性能较hashMap低。
2）hashTable的初始容量为11，扩容规则为size=oldSize*2+1
3）hashTable的计算index的规则为：（hash&0x7FFFFFFF）%tab.length
4）hashTabnle和hashMap的迭代器不同
5）实际生产中，HashTable基本已弃用，因为在单线程环境中，性能不如HashMap，在多线程环境中，其为保证线程安全直接给add、put方法加了一把synchronized大锁，相当于强制串行性能很差。
HashSet
HashSet的底层就是借助HashMap实现的，像add等很多方法都是直接调用的HashMap中功能相近的方法来实现的。HashSet实现了Set接口，所以不允许重复元素。
HashSet是如何检查重复的？
HashSet执行add时，会计算对象的hashcode值，如果hashcode和Set中其他对象的hashcode不相等，则认为没有重复元素，可以add。如果已经存在hashcode相等的对象，则会使用equals比较新老对象的值，如果两者相同equals，则认为新对象为重复元素，不再添加到Set中。
线程安全
Haseset的底层基于HashMap，TreeSet底层基于TreeMap，LinkedHashSet底层基于LinkedHashMap，普通的Map不是线程安全的，所以普通的set也不是线程安全的。
构建线程安全的set可以使用Collections.synchronizedSet()或者JUC包里面的CopyOnWriteArraySet，或者guava的ConcurrentHashSet。
ConcurrentHashMap
JDK1.7中的ConcurrentHashMap，采用的是分段锁的思想，底层数据结构是数组+链表。
即在ConcurrentHashMap中存在多段数据(Segment数组)，每段数据中包含多个数据(HashEntry数组)，每段数据有一个单独的锁，这样不同段的数据在并发put时就不会互相竞争了，提升并发效率。在并发read时不需要加锁，因为read过程中涉及到的共享变量都用volitale修饰，volitale保证内存可见性，因此读取到的数据不会是过期的。
寻址方式：
在读取某个key时，先取key的hash值，然后对hash值的高N位取模，从而得到key属于哪一个segment，然后再同操作HashMap一样操作这个segment。
1、采用分段的数组+链表，把整个Map分为多个Segment，每个Segment继承了ReentrantLock可重入锁，来达到既能保证线程安全，又能提高吞吐能力的目的。默认的Segment数量时16.
2、ConcurrentHashMap的读操作不加锁，但是仍然保证value是最新的，因为HashEntry的value变量是volatitle修饰的。
3、有些方法也是需要锁整张Map的，入size和containsValue，先按顺序锁住所有的segment，然后再按顺序释放。
4、ConcurrentHashMap的扩容是段内扩容，每个segment类似于一个hashMap。在插入前执行扩容，避免了无效扩容。
参考：http://www.jasongj.com/java/concurrenthashmap/
JDK1.8中的ConcurrentHashMap放弃了1.7中的分段锁segment思想，改用了CAS+Synchronized思想，底层数据结构是数组+链表+红黑树，但从底层数据结构上看，JDK1.8中的HashMap和ConcurrentHashMap相似。
哈希冲突解决
拉链法
将哈希值相同的元素构成一个单链表，将单链表的表头指针存放在哈希表的单元中。jdk中对于链表长度小于8的链表，采用拉链法解决HashMap中的哈希碰撞，长度大于8则转换为红黑树。适用于经常进行插入和删除的情况。
开放定址法
从发生冲突的单元起，按照一定的次序，从哈希表中找到一个空闲的单元，然后把发生冲突的元素放入该单元。寻找空闲单元的次序可以使线性的逐个判断，可以是有规则的跳跃判断。
再哈希法
准备多个不同的哈希函数，hash1发生冲突时计算hash2，直到不产生冲突。这种方法散列效果好，但是增加计算时间。
建立公共溢出去法
将哈希表分为基本区和溢出区两部分，凡是和基本区发生冲突的元素，一律放入溢出区。
比较拉链法和开放定址法
拉链法
优点：对于元素总数频繁变化的情况，支持动态调整，无需扩容，删除时也不会有内存浪费。增加删除都是操作指针即可，比较方便。
缺点：由于使用指针，记录不容易进行序列化；存储的结果是随机分配在内存中的，相比数组这样紧凑的数据类型，访问会带来额外时间开销。
开放定址法
优点：记录更容易进行序列化；如果记录总数可以预知，理论上可以创造完美的哈希函数，这时处理数据的效率是很高的。
缺点：元素总数不能超过数组的长度，否则需要扩容，而扩容的成本很大；除非满数组的情况，否则必然存在空槽，当数组容量很大时，浪费也会多；删除比较麻烦。（比如需要删除记录a，记录b是在a之后插入桶数组的，但是和记录a有冲突，是通过探测序列再次跳转找到的地址，所以如果直接删除a，a的位置变为空槽，而空槽是查询记录失败的终止条件，这样会导致记录b在a的位置重新插入数据前不可见，所以不能直接删除a，而是设置删除标记。这就需要额外的空间和操作。）
若有收获，就点个赞吧
0 人点赞
