数组和链表是如何组织工作的？
数组：查询快，增删慢
链表：查询慢，增删快
概念：
数组里的元素是连续的
链表的每个元素都存储了下一个元素的地址，从而使得一系列的随机的内存地址串在了一起，只要有足够的内存空间，就能为链表分配内存。
解释：
数组查询元素：知道第一个按顺序遍历就行
数组增加元素：如果需要给index为10的位置添加，则从index为11的位置开始右移，然后再添加。
数组删除元素：如果需要删除index为10的位置，则从index为11的位置开始左移
链表查找：当同时读取所有元素时，链表的效率很高，读第一个，读第二个，以此类推。
但当你需要跳跃，链表的效率就很低了，每次都必须从第一个开始查找
链表增加元素：只需要修改它前面的那个元素指向的地址就可以了
链表删除元素：只需要将前一个元素指向的地址更改即可
什么是HashMap？为什么用到它？
为什么用HashMap？HashMap是数组+链表的形式，集合了数组的查询快速的优点，和链表增删快速的优点。效率高。
int hash是什么？有什么作用？
hash是如何计算的？
线性运算，时间非常快，一次hash运算+一次数值运算，得到 key->数组的对接
key通过hash运算，得到一个int型的hash，然后int型的hash对tab取余数（%），就得到tab数组的下标区间。
HashMap底层是数组+链表的方式，在什么情况下链表转为红黑树？
jdk1.8之后，HashMap底层由【数组+链表】的方式转变为【数组+链表/红黑树】的方式，但是什么情况下才会由链表转为红黑树呢？
只有当数组长度大于64，且链表长度达到8的时候。
最小树形化容量阈值：即 当哈希表中的容量 > 该值时，才允许树形化链表 （即 将链表 转换成红黑树），否则，若桶内元素太多时，则直接扩容，而不是树形化， 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD（默认值），即64。
什么是hash碰撞（冲突）？怎么处理hash碰撞（冲突）？
当上方hash计算后，最后得到的tab数组的下标是同一个，就是hash碰撞。
当hash碰撞之后，它会判断新的hash与旧的是否相同，然后两者的key是否相同，当key也相同的话，新的就会覆盖老的。这就是为什么不能用相同的key，key必须唯一。如果key不相同，那么就加入一个next记录下一个节点。
HashMap的工作原理是什么？
HashMap的put()方法的工作原理是什么？
把key，通过hash计算，得到hashbode，然后通过取余得到tab的下标，再通过下标去当前的下标链表里比对key，如果比对上了，就覆盖。比对不上，就插入链表的尾部。
HashMap的get()方法的工作原理是什么？
把查找的key，通过hash计算，得到hashcode，然后通过取余得到tab的下标。再通过下标去当前下标的链表里面比对key，如果比对上了，就返回，比对不上就返回null；
当两个对象的hashcode相同会发生什么？
会产生hash冲突，为了解决hash冲突，会形成链表。这样添加和删除的效率会降低。（jdk1.6的时候，是加在链表头，jdk1.8的时候是加在尾部。）
如果两个键的hashcode相同，如何获取值对象？
当hashcode相同，我们判断code的同时，还会轮询，判断key是否相同，当key也相同的时候，就会获取到值。
如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
如果超过了负载因子定义的容量，就会扩容。然后重新计算hash（rehash）
重新调整HashMap大小存在什么问题？如何优化？
存在的问题：重新调整HashMap大小，意味着更多空间被浪费。每次增长都*2。所有以前的节点，重新计算hash，然后放入。但是如果需要放置的内容很多，而hashmap的初始值很小，就会频繁地触发阈值，然后调整大小，每次都要重新计算hash（rehash）并放入。
优化：hashmap的默认大小是16，当我们比较明确要放入内容的数量的时候（比如700个），这时候我们只需要初始化的时候给hashmap一个确定的值就好，不然此时就会触发6次rehash。例如new HashMap(1024)，一般为2的n次方。此时如果是new HashMap(512)，那么就会触发阈值，然后rehash。
为什么String，Interger这样的wrapper类适合作为键？
因为String和Interger中，实现了hashcode；一个内容要作为一个键，就必须要实现hashcode。
为什么hashcode计算复杂？
我们可以使用自定义的对象作为键吗？
可以使用自定义对象作为键，只要这个自定义对象实现了hashcode，不实现hashcode的话，hash冲突的概率就会很高。
Hash原理？
整个hash表里面去增加节点，删除节点
Hash值怎么计算？
通过一系列的位运算得到值
什么是hash碰撞？
通过hash运算得出来的hash值，然后通过取余得到tab的下标相等；就是hash碰撞。
为什么需要加载因子？
如果数组大小为n，加载因子DEFAULT_LOAD_FACTOR=0.75。
则当放入hashmap的内容数量超过 nDEFAULT_LOAD_FACTOR的阈值的时候，就会产生扩容，即原数组大小2。
网友评论