数据结构面试专题详解，收藏一下吧_数据结构 面试题

至于为什么要扩容，如果不扩容，HashMap中数组处的链表会越来越长，这样查找效率就会大大降低。

6.1 HashMap如何put数据（从HashMap源码角度讲解）？

当我们使用put(key, value)存储对象到HashMap中时，具体实现步骤如下：

• 先判断table数组是否为空，为空以默认大小构建table，table默认空间大小为16

• 计算key的hash值，并计算hash&(n-1)值得到在数组中的位置index，如果该位置没值即table[index]为空，则直接将该键值对存放在table[index]处。

• 如果table[index]处不为空，说明发生了hash冲突，判断table[index]处结点是否是TreeNode(红黑树结点)类型数据，如果是则执行putTreeVal方法，按红黑树规则将键值对存入；

• 如果table[index]是链表形式，遍历该链表上的数据，将该键值对放在table[index]处，并将其指向原index处的链表。判断链表上的结点数是否大于链表最大结点限制（默认为8），如果超过了需执行treeifyBin()操作，则要将该链表转换成红黑树结构。

• 判断HashMap中数据个数是否超过了（最大容量*装载因子），如果超过了，还需要对其进行扩容操作。

6.2 HashMap如何get数据？

get(key)方法获取key的hash值，计算hash&(n-1)得到在链表数组中的位置first=table[hash&(n-1)]，先判断first（即数组中的那个）的key是否与参数key相等，不等的话，判断结点是否是TreeNode类型，是则调用getTreeNode(hash, key)从二叉树中查找结点，不是TreeNode类型说明还是链表型，就遍历链表找到相同的key值返回对应的value值即可。

6.3 当两个对象的hashcode相同，即发生碰撞时，HashMap如何处理

当两个对象的hashcode相同，它们的bucket位置相同，hashMap会用链表或是红黑树来存储对象。Entry类里有一个next属性，作用是指向下一个Entry。第一个键值对A进来，通过计算其key的hash得到index，记做Entry[index]=A。一会又进来一个键值对B，通过计算其key的hash也是index，HashMap会将B.next=A, Entry[index]=B.如果又进来C，其key的hash也是index,会将C.next=B, Entry[index]=C.这样bucket为index的地方存放了A\B\C三个键值对，它们能过next属性链在一起。数组中存储的是最后插入的元素，其他元素都在后面的链表里。

6.4 如果两个键的hashcode相同，如何获取值对象？

当调用get方法时，hashmap会使用键对象的hashcode找到bucket位置，找到bucket位置后，会调用key.equals()方法去找到链表中正确的节点，最终找到值对象。

6.5 hashMap如何扩容

HashMap默认负载因为是0.75，当一个map填满了75%的bucket时，和其他集合类一样，将会创建原来HashMap大小两倍的bucket数组，来重新调整HashMap的大小，并将原来的对象放入新的bucket数组中。

在jdk1.7及以前，多线程扩容可能出现死循环。因为在调整大小过程中，存储在某个bucket位置中的链表元素次序会反过来，而多线程情况下可能某个线程翻转完链表，另外一个线程又开始翻转，条件竞争发生了，那么就死循环了。

而在jdk1.8中，会将原来链表结构保存至节点e中，将原来数组中的位置设为null，然后依次遍历e，根据hash&n是否为0分成两条支链，保存在新数组中。如果多线程情况可能会取到null值造成数据丢失。

7、ConcurrentHashMap的实现原理

1）jdk1.7及以前：一个ConcurrentHashMap由一个segment数组和多个HashEntry组成，每一个segment都包含一个HashEntry数组, Segment继承ReentrantLock用来充当锁角色，每一个segment包含了对自己的HashEntry的操作，如get\put\replace操作，这些操作发生时，对自己的HashEntry进行锁定。由于每一个segment写操作只锁定自己的HashEntry，可以存在多个线程同时写的情况。

jdk1.8以后：ConcurrentHashMap取消了segments字段，采用transient volatile HashEntry<K, V> table保存数据，采用table数组元素作为锁，实现对每一个数组数据进行加锁，进一小减少并发冲突概率。ConcurrentHashMap是用Node数组+链表+红黑树数据结构来实现的，并发制定用synchronized和CAS操作。

**2）**Segment实现了ReentrantLock重入锁，当执行put操作，会进行第一次key的hash来定位Segment的位置，若该Segment还没有初始化，会通过CAS操作进行赋值，再进行第二次hash操作，找到相应的HashEntry位置。

8、ArrayMap和HashMap的对比

**1)**存储方式不一样，HashMap内部有一个Node<K,V>[]对象，每个键值对都会存储到这个对象里，当用put方法添加键值对时，会new一个Node对象，tab[i] = newNode(hash, key, value, next);

ArrayMap存储则是由两个数组来维护，int[] mHashes; Object[] mArray; mHashes数组中保存的是每一项的HashCode值，mArray存的是键值对，每两个元素代表一个键值对，前面保存key，后面保存value。mHashes[index]=hash; mArray[index<<1]=key; mArray[(index<<1)+1]=value;

ArrayMap相对于HashMap，无需为每个键值对创建Node对象，且在数组中连续存放，更省空间。

**2）**添加数据时扩容处理不一样，进行了new操作，重新创建对象，开销很大；而ArrayMap用的是copy数据，所有效率相对高些；

**3）**ArrayMap提供了数组收缩功能，在clear或remove后，会重新收缩数组，释放空间；

**4）**ArrayMap采用二分法查找，mHashes中的hash值是按照从小到大的顺序连续存放的，通过二分查找来获取对应hash下标index，去mArray中查找键值对。mHashes中的index2是mArray中的key下标，index2+1为value的下标，由于存在hash碰撞情况，二分查找到的下标可能是多个连续相同的hash值中的任意一个，此时需要用equals比对命中的key对象是否相等，不相等，应当从当前index先向后再向前遍历所有相同hash值。

**5）**sparseArray比ArrayMap进一步优化空间，SparseArray专门对基本类型做了优化，Key只能是可排序的基本类型，如int\long，对value，除了泛型Value，还对每种基本类型有单独实现，如SparseBooleanArray\SparseLongArray等。无需包装，直接使用基本类型值，无需hash，直接使用基本类型值索引和判断相等，无碰撞，无需调用hashCode方法，无需equals比较。SparseArray延迟删除。

9、HashTable实现原理

Hashtable中的无参构造方法Hashtable()中调用了this(11, 0.75f)，说明它默认容量是11，加载因子是0.75,在构造方法上会new HashtableEntry<?, ?>[initialCapacity]; 会新建一个容量是初始容量的HashtableEntry数组。

HashtableEntry数组中包含hash\Key\Value\next变量，链表形式，重写了hashCode和equals方法。Hashtable所有public方法都在方法体上加上了synchronized锁操作，说明它是线程安全的。

它还实现了Serializable接口中的writeObject和readObject方法，分别实现了逐行读取和写入的功能，并且加了synchronized锁操作。

（1） put(Key, Value)方法

• 先判断value是否为空，为空抛出空指针异常；

• 根据key的hashCode()值，计算table表中的位置索引(hash&0x7FFFFFFF)%tab.length值index，如果该索引处有值，再判断该索引处链表中是否包含相同的key，如果key值相同则替换旧值。

• 如果没有相同的key值，调用addEntry方法，在addEntry中判断count大小是否超过了最大容量限制，如果超过了需要重新rehash()，容量变成原来容量*2+1，将原表中的值都重新计算hash值放入新表中。再构造一个HashtableEntry对象放入相应的table表头，如果原索引处有值，则将table[index].next指向原索引处的链表。

（2）get方法

根所key.hashCode()，计算它在table表中的位置，(hash&0x7FFFFFFF)%tab.length，遍历该索引处表的位置中是否有值，是否存在链表，再判断是key值和hash值是否相等，相等则返回对应的value值。

10、HashMap和HashTable的区别

**1）**Hashtable是个线程安全的类，在对外方法都添加了synchronized方法，序列化方法上也添加了synchronized同步锁方法，而HashMap非线程安全。这也导致Hashtable的读写等操作比HashMap慢。

**2）**Hashtable不允许值和键为空，若为空会抛出空指针。而HashMap允许键和值为空；

**3）**Hashtable根据key值的hashCode计算索引，(hash&0x7FFFFFFF)%tab.length，保证hash值始终为正数且不超过表的长度。而HashMap中计算索引值是通过hash(key)&(tab.length-1)，是通过与操作，计算出在表中的位置会比Hashtable快。

**4）**Hashtable容量能为任意大于等于1的正数，而HashMap的容量必须为2^n，Hashtable默认容量为11，HashMap初始容量为16

**5）**Hashtable每次扩容，新容量为旧容量的2倍+1，而HashMap为旧容量的2倍。

11、HashMap与HashSet的区别

HashSet底层实现是HashMap,内部包含一个HashMap<E, Ojbect> map变量

private transient HashMap<E,Object> map;

一个Object PRESENT变量（当成插入map中的value值）

private static final Object PRESENT = new Object();

HashSet中元素都存到HashMap键值对的Key上面。具体可以查看HashSet的add方法，直接调用了HashMap的put方法，将值作为HashMap的键，值用一个固定的PRESENT值。

public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

HashSet没有单独的get方法，用的是HashMap的。HashSet实现了Set接口，不允许集合中出现重复元素，将对象存储进HashSet前，要先确保对象重写了hashCode()和equals方法，以保证放入set对象是唯一的。

12、HashSet与HashMap怎么判断集合元素重复？

HashMap在放入key-value键值对是，先通过key计算其hashCode()值，再与tab.length-1做与操作，确定下标index处是否有值，如果有值，再调用key对象的equals方法，对象不同则插入到表头，相同则覆盖；

HashSet是将数据存放到HashMap的key中，HashMap是key-value形式的数据结构，它的key是唯一的，HashSet利用此原理保证放入的对象唯一性。

13、集合Set实现Hash怎么防止碰撞

HashSet底层实现是HashMap，HashMap如果两个不同Key对象的hashCode()值相等，会用链表存储，HashSet也一样。

14、ArrayList和LinkedList的区别，以及应用场景

ArrayList底层是用数组实现的，随着元素添加，其大小是动态增大的；在内存中是连续存放的；如果在集合末尾添加或删除元素，所用时间是一致的，如果在列表中间添加或删除元素，所用时间会大大增加。通过索引查找元素速度很快。适合场合：查询比较多的场景

LinkedList底层是通过双向链表实现的，LinkedList和ArrayList相比，增删速度快，但查询和修改值速度慢。在内存中不是连续内存。场景：增删操作比较多的场景。

• 二叉树的深度优先遍历和广度优先遍历的具体实现
• 堆的结构
• 堆和树的区别
• 堆和栈在内存中的区别是什么(解答提示：可以从数据结构方面以及实际实现方面两个方面去回答)？
• 什么是深拷贝和浅拷贝
• 手写链表逆序代码
• 讲一下对树，B+树的理解
• 讲一下对图的理解
• 判断单链表成环与否？
• 链表翻转（即：翻转一个单项链表）
• 合并多个单有序链表（假设都是递增的）

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数Android工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Android移动开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Android开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录大纲截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且后续会持续更新

如果你觉得这些内容对你有帮助，可以添加V获取：vip204888 （备注Android）

总结

首先是感觉自己的基础还是不够吧，大厂好像都喜欢问这些底层原理。

另外一部分原因在于资料也还没有看完，一面时凭借那份资料考前突击恶补个几天居然也能轻松应对（在这里还是要感谢那份资料，真的牛），于是自我感觉良好，资料就没有怎么深究下去了。

之前的准备只涉及了Java、Android、计网、数据结构与算法这些方面，面对面试官对其他基础课程的考察显得捉襟见肘。

下一步还是要查漏补缺，进行针对性复习。

最后的最后，那套资料这次一定要全部看完，是真的太全面了，各个知识点都涵盖了，几乎我面试遇到的所有问题的知识点这里面都有！希望大家不要犯和我一样的错误呀！！！一定要看完！

这里面都有！希望大家不要犯和我一样的错误呀！！！一定要看完！**
[外链图片转存中…(img-PBy0PH8w-1712005256630)]

[外链图片转存中…(img-OYltjg18-1712005256630)]

[外链图片转存中…(img-7iTJx5k0-1712005256630)]

本文已被CODING开源项目：《Android学习笔记总结+移动架构视频+大厂面试真题+项目实战源码》收录