当前位置： java数据结构链表例子-链表 结构
今天的文章纯粹是从面试的角度出发，以面试问题的答案为线索，然后回顾整个Java集合框架，希望能帮助到大家在面试中获胜。
第一张图：
面试官提问的时候，我会先把问题分类，锁定这个知识点在我的知识体系中的位置，然后展开去思考这块的重点内容。 你还想问什么？
这样自己的思路就不会混乱，也可以预测面试官接下来的问题，也可以引导面试官问你精心准备的问题。 这次面试本质上是你在主导，你在炫耀你的扎实基础。 知识和良好的沟通技巧。
其实我在LRU的那篇文章里提到了这个观点，然后有读者问我会不会被面试官识破？
A：看到了怎么办？ 面试官见过无数人，看出来也是有可能的，但他只会笑笑，认为这个学生很努力。
认真准备面试，既是对面试官个人时间的尊重，也体现了你对这家公司的兴趣。 这样的员工不正是每个公司都想要的吗？
好了，进入正题，今天就来解决这9道面试题吧。
1. ArrayList 与 LinkedList
有很多方法可以问这个问题java数据结构链表例子，比如
一切都保持不变。
第一个结论是：
两者在实现层面的区别在于：
数组和链表最大的区别是数组可以被随机访问（random access）。
这个特性使得可以在O(1)时间内通过下标得到数组中任意位置的数，而链表做不到，只能从头开始逐一遍历。
两者在增删改查操作上的区别：
但是，事实上，你不能忽视寻找元素的时间。 . . 虽然 LinkedList 可以在 O(1) 时间内插入和删除元素，但你必须先找到位置！
没有例子吗，修这个零件只需要1美元，但是找这个零件要9999美元。 我们平时的bug修复也是如此，重点是找根源的过程。
而如果是放在最后操作，ArrayList在数据量大的时候速度会更快。
事实上，LinkedList 是很多性能问题的 bug，那为什么呢？
由于ListNode在物理内存上是不连续的，它使用了很多小的内存碎片，会影响很多进程的性能和cache-locality（局部性）； 所以即使理论时间复杂度和ArrayList一样，也导致实际上比ArrayList慢很多。
2. ArrayList 与 Vector
回答：
Vector是线程安全的，而ArrayList不是线程安全的； 扩容时扩容多少的区别，文走走说数据增长方式不同，
回头看这张照片，
Vector和ArrayList一样，也是继承自java.util.AbstractList，底层也是用数组实现的。
但它现在已被弃用，因为它是线程安全的。 任何好处都是有代价的。 线程安全的代价是效率低下，在一些系统中很容易成为瓶颈，所以现在大家不再在数据结构层面加上synchronized，而是把这个任务交给我们程序员。
那么你怎么知道要扩展多少呢？
看源码：
这是Vecotr的扩容实现，因为通常没有定义capacityIncrement，所以默认是capacity的两倍。
对比
这是ArrayList的扩展实现。 算术右移操作就是将这个数的二进制数向右移动一位，补上最左边的符号位。 但是因为容量没有负数，所以还是填0。
右移一位的效果是除以2，那么定义的新容量是原来容量的1.5倍。
3. ArrayDeque 与 LinkedList
首先，有必要了解一下它们之间的关系：
回答：
ArrayDeque是可展开数组，LinkedList是链表结构； ArrayDeque 不能存储空值，但 LinkedList 可以； ArrayDeque在头部和尾部进行增删操作时效率更高，而LinkedList只有当要移除中间的一个元素时，找到元素后的移除是O(1)； ArrayDeque 在内存使用方面更高效。 所以，只要不是一定要存null值，就选ArrayDeque吧！
那么如果一个很资深的面试官问你，什么情况下应该选择使用LinkedList呢？
答：Java 6之前。因为ArrayDeque是Java 6之后才有的。为了版本兼容，我们在实际工作中不得不做一些妥协。
4.HashSet实现原理
回答：
HashSet是基于HashMap实现的。 底层使用Hashmap的key来存储元素。 主要特点是无序，基本操作都是O(1)时间复杂度，速度很快。 所以它的实现原理可以用HashMap来解释。
5.HashMap实现原理
回答：
具体来说，
对于HashMap中的每一个key，先通过hash函数计算出一个hash值，这个hash值代表了桶中的个数，而“桶”其实是通过一个数组来实现的，只是桶可能比数组大，所以将哈希值取模到数组的长度得到它在数组中的索引，并像这样放入数组中。
这是一个理想的HashMap，但在现实中，不同的元素可能会计算出相同的哈希值，这就是哈希碰撞，即多个键对应同一个桶。
Java为了解决hash碰撞，采用了Separate chaining的解决方案，就是在碰撞的地方加一条链，就是上面说的链表或者红黑树。
关于put()和get()这两个重要API的具体运行过程和原理，可以在公众号后台回复“HashMap”阅读文章。
6.HashMap 与 HashTable
回答：
Hashtable是线程安全的，HashMap不是线程安全的；
HashMap允许key中有空值，但是Hashtable不允许。 这样做的好处是你可以给一个默认值。
其实HashMap和Hashtable的关系就像ArrayList和Vector，StringBuilder和StringBuffer的关系。
Hashtable是早期JDK提供的接口，HashMap是新版本。 新版本的这些改进都是因为在Java 5.0之后，允许数据结构不考虑线程安全，因为在实际工作中我们发现在数据结构层面是不需要加锁的，有系统中用于锁定和释放锁的开销。 内部锁有时会成为程序的瓶颈。
因此，HashMap、ArrayList、StringBuilder不再考虑线程安全的问题，性能得到了很大的提升。
7、为什么改equals()一定要改hashCode()？
回答：
首先基于一个假设：任意两个对象的hashCode是不同的。 也就是说，哈希函数是有效的。
那么在这种情况下，如果两个对象相等，如果你不重写hashCode()java数据结构链表例子，计算出的哈希值就会不同，就会去到不同的桶，就会迷失在茫茫人海中。 如果不能再识别，则与equals()的条件矛盾，证明完成。
hashCode() 决定了key放入这个bucket中的个数，也就是数组中的index；
equals() 用于比较两个对象是否相同。
8. 如何解决哈希冲突？
一般来说，哈希冲突的解决方案有两种：
Java中使用的是第一种Separate chaining，即在发生碰撞的bucket后面加一条“链”进行存储。
那么这个“链”使用的具体数据结构是什么，不同的版本略有不同，如上文所述：
（话说这个真的很喜欢考，很多面试都问过，面试官问为什么超过“8”就用红黑树）
第二种方法，open addressing，也是一个很重要的思想，因为在真正的分布式系统中，很多地方都会用到hash的思想，但是seprate chaining并不适用。
这种方法是顺序搜索。 如果桶已经被占用，则继续以“某种方式”寻找下一个未被占用的桶，直到找到第一个空的桶。
如图所示，John Smith和Sandra Dee发生hash冲突，两人都被计算到152号桶，于是Sandra转到下一个空位——153号桶，当然也会影响后面的keys：Ted Baker计算结果，本来应该放在153号的，但是因为已经被Sandra占据了，不得不去下一个空位，所以就去了154号。
这种方法称为Linear probing，如上图所示，一个一个地寻找下一个空位。 当然还有其他的方法，比如求平方数Double hashing。
9.收藏与收藏
这两者看似相似，实则相差甚远，就像好人与好人卡的区别。
集合是
而Collections是一个实用类，一个对集合的操作类，它提供了一些静态方法供我们使用，比如：
点击观看，点赞支持我
上一篇 
