问与答 · JAVA基础

2018-07-12 本文已影响0人南山羊

emm...

HashMap的源码，实现原理，JDK8中对HashMap做了怎样的优化。

数组：数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难；
链表：链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。链表的特点是：寻址困难，插入和删除容易。
哈希表：那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构，这就是我们要提起的哈希表。哈希表（(Hash table）既满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便。哈希表有多种不同的实现方法，我们可以理解为“链表的数组”。

哈希表是由 数组 + 链表 组成的，一个长度为 16 的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过 hash(key)%len 获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中， 12%16=12 , 28%16=12 , 108%16=12 , 140%16=12 。所以 12 、 28 、 108 以及 140 都存储在数组下标为 12 的位置。

JDK8中，HashMap 加入了红黑树的使用，当节点长度大于8并且数组的长度大于64时，该节点链表就会转化成红黑树。数组长度小于64并且节点长度大于8时，仅仅扩容，并不会将链表转换成红黑树。

HaspMap扩容是怎样扩容的，为什么都是2的N次幂的大小。

HashMap计算 Key 值在数组中的位置是使用 Key.hashcode() 与 数组长度减一 进行 & 运算。当长度是 2 的N次幂时，数组长度减一 的二进制实则为 N-1个1。进行与或运算时，能够快速取到小于自己的一个整数。比 % 取模速度更快。

HashMap，HashTable，ConcurrentHashMap的区别。

HashMap是非线程安全的，HashTable是线程安全的，内部的方法基本都经过synchronized修饰。因为同步、哈希性能等原因，性能肯定是HashMap更佳，因此HashTable已被淘汰。
HashMap的键和值都允许有null存在，而HashTable则都不行，在HashTable中put进的键值只要有一个null，直接抛出NullPointerException。
ConcurrentHashMap是线程安全的HashMap的实现。HashTable里使用的是synchronized关键字，这其实是对对象加锁，锁住的都是对象整体，当Hashtable的大小增加到一定的时候，性能会急剧下降，因为迭代时需要被锁定很长的时间。
ConcurrentHashMap引入了分割(Segment)，上面代码中的最后一行其实就可以理解为把一个大的Map拆分成N个小的HashTable，在put方法中，会根据hash(paramK.hashCode())来决定具体存放进哪个Segment，如果查看Segment的put操作，我们会发现内部使用的同步机制是基于lock操作的，这样就可以对Map的一部分（Segment）进行上锁，这样影响的只是将要放入同一个Segment的元素的put操作，保证同步的时候，锁住的不是整个Map（HashTable就是这么做的），相对于HashTable提高了多线程环境下的性能，因此HashTable已经被淘汰了。

极高并发下HashTable和ConcurrentHashMap哪个性能好，如何实现的。

上个问题已经回答了，在极高并发下ConcurrentHashMap的性能要好于HashTable，因为ConcurrentHashMap采用的是分段锁，不会造成整个对象锁住，在高并发时性能明显好于Hashtable。

HashMap在高并发下如果没有处理线程安全会有怎样的安全隐患，具体表现是什么。

多线程put时可能导致元素丢失，原因：当多个线程同时执行addEntry(hash,key ,value,i)时，如果产生哈希碰撞，导致两个线程得到同样的bucketIndex去存储，就可能会发生元素覆盖丢失的情况
多线程put时可能会导致get无限循环，具体表现为CPU使用率100%；原因：在向HashMap put元素时，会检查HashMap的容量是否足够，如果不足，则会新建一个比原来容量大两倍的Hash表，然后把数组从老的Hash表中迁移到新的Hash表中，迁移的过程就是一个rehash()的过程，多个线程同时操作就有可能会形成循环链表，所以在使用get()时，就会出现Infinite Loop的情况。

java中四种修饰符的限制范围。

private: Java语言中对访问权限限制的最窄的修饰符，一般称之为“私有的”。被其修饰的属性以及方法只能被该类的对象访问，其子类不能访问，更不能允许跨包访问。
default：即不加任何访问修饰符，通常称为“默认访问权限“或者“包访问权限”。该模式下，只允许在同一个包中进行访问。
protected: 介于public 和 private 之间的一种访问修饰符，一般称之为“保护访问权限”。被其修饰的属性以及方法只能被类本身的方法及子类访问，即使子类在不同的包中也可以访问。
public： Java语言中访问限制最宽的修饰符，一般称之为“公共的”。被其修饰的类、属性以及方法不仅可以跨类访问，而且允许跨包访问。

Object类中的方法。

clone()

clone()函数的用途是用来另存一个当前存在的对象。

hashCode()和equals()

equals()用于确认两个对象是否相同，hashCode()用于获取对象的哈希值，哈希值相同的对象不一定equals()，equale()返回true的两个对象一定相同。

toString()

toString()返回一个String对象，用来标识自己。

getClass()

getClass()返回一个Class对象。因为返回的是一个class对象,后面可以跟class类的方法。用的是谁的构造函数，那么getClass返回的就是谁的类型，getClass()经常用于java反射机制。

finalize()

这个函数在进行垃圾回收的时候会用到，匿名对象回收之前会调用到。