阿里面试90%以上会问到的数据结构;HashMap

简介: BAT面试必问;关于hashmap,你知道多少?你知道hashmap的工作原理吗?1.该问题很有深度2.能答出多少决定岗位和薪资.3.问题的方式多种多样一.首先我们了解下HashMap是什么HashMap是Java常用的用来储存键值对的数据结构,它是线程不安全的,可以储存null键值,这些大家经常用,也都知道,接下来根据源码分析一下HashMap的实现。

BAT面试必问;

关于hashmap,你知道多少?你知道hashmap的工作原理吗?

1.该问题很有深度

2.能答出多少决定岗位和薪资.

3.问题的方式多种多样

一.首先我们了解下HashMap是什么

HashMap是Java常用的用来储存键值对的数据结构,它是线程不安全的,可以储存null键值,这些大家经常用,也都知道,接下来根据源码分析一下HashMap的实现。

1、实现原理

HashMap采用数组散列+链表的方式来储存键值对,键值对的对象实现如下:

static class Entry<K,V> implements Map.Entry<K,V> { 
 final K key; 
 V value; 
 Entry<K,V> next; 
 final int hash; 
 …… 
} 

通过一个Entry的数组table就实现了多个对象的保存,使用哈希值和键值解决了在插入和查找时的冲突。

2、put方法,写入键值对

public V put(K key, V value){
 //如果 key 为 null,调用 putForNullKey 方法写入null键的值
 if (key == null){
 return putForNullKey(value);
}
//根据 key 的 keyCode 计算 Hash 值 
int hash = hash(key.hashCode());
//查找hash值在table中的索引
int i = indexFor(hash, table.length);
// 如果 i 索引处的 Entry 不为 null,通过循环不断遍历链表查找是否在链表中有相同key的Entry
for (Entry<K,V> e = tablei; e != null; e = e.next) {
 Object k;
 //找到与插入的值的key和hash相同的Entry
 if (e.hash == hash && ((k = e.key) == key|| key.equals(k)){
 //key值相同时直接替换value值,跳出函数
 V oldValue = e.value;
 e.value = value; e.recordAccess(this); return oldValue; } }
// 如果 i 索引处的 Entry 为 null 或者key的hash值相同而key不同 ,则需要新增Entry
modCount++; 
// 将 key、value 添加到 i 索引处
addEntry(hash, key, value, i); 
return null; 
} 

在put方法中解决hash碰撞的方式很清楚,即当两个entry的hash值相同时,需要对key值是否相同进行判断,只有key和hash都相同,才能进行修改,否则认为不是同一个entry。

3.addEntry的实现

代码:

void addEntry(int hash, K key, V value, int bucketIndex) { // 获取指定 bucketIndex 索引处的 Entry
Entry<K,V> e = tablebucketIndex; 
tablebucketIndex = new Entry<K,V>(hash, key, value, e); // 如果 Map 中的 key-value 对的数量超过了极限
if (size++ >= threshold)
 resize(2 table.length);
} 

在创建新Entry时如果table的bucketIndex处有元素的话,创建时需要将entry的next设置为原先存储的元素。

二,HashMap工作原理

以下为目录,有需要完整进阶视频可以加Android进阶群;701740775免费获取

1.目录

 

2.顺序表与链表

 

3.Hsh表

 

 

 

4.Hash源码

 

5.碰撞

 

需要完整进阶视频详解可以加Android进阶群;701740775免费获取!

附录Android高级技术大纲和进阶视频;

 

相关文章
|
13天前
|
存储 关系型数据库 MySQL
阿里面试:为什么要索引?什么是MySQL索引?底层结构是什么?
尼恩是一位资深架构师,他在自己的读者交流群中分享了关于MySQL索引的重要知识点。索引是帮助MySQL高效获取数据的数据结构,主要作用包括显著提升查询速度、降低磁盘I/O次数、优化排序与分组操作以及提升复杂查询的性能。MySQL支持多种索引类型,如主键索引、唯一索引、普通索引、全文索引和空间数据索引。索引的底层数据结构主要是B+树,它能够有效支持范围查询和顺序遍历,同时保持高效的插入、删除和查找性能。尼恩还强调了索引的优缺点,并提供了多个面试题及其解答,帮助读者在面试中脱颖而出。相关资料可在公众号【技术自由圈】获取。
|
12天前
|
存储 Java
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
23 1
|
14天前
|
存储 Java 开发者
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【10月更文挑战第17天】本文深入探讨了Java中HashMap和TreeMap两种Map类型的特性和应用场景。HashMap基于哈希表实现,支持高效的数据操作且允许键值为null;TreeMap基于红黑树实现,支持自然排序或自定义排序,确保元素有序。文章通过具体示例展示了两者的实战应用,帮助开发者根据实际需求选择合适的数据结构,提高开发效率。
45 2
|
20天前
|
消息中间件 存储 canal
阿里面试:canal+MQ,会有乱序的问题吗?
本文详细探讨了在阿里面试中常见的问题——“canal+MQ,会有乱序的问题吗?”以及如何保证RocketMQ消息有序。文章首先介绍了消息有序的基本概念,包括全局有序和局部有序,并分析了RocketMQ中实现消息有序的方法。接着,针对canal+MQ的场景,讨论了如何通过配置`canal.mq.partitionsNum`和`canal.mq.partitionHash`来保证数据同步的有序性。最后,提供了多个与MQ相关的面试题及解决方案,帮助读者更好地准备面试,提升技术水平。
阿里面试:canal+MQ,会有乱序的问题吗?
|
11天前
|
存储 Java 程序员
Java面试加分点!一文读懂HashMap底层实现与扩容机制
本文详细解析了Java中经典的HashMap数据结构,包括其底层实现、扩容机制、put和查找过程、哈希函数以及JDK 1.7与1.8的差异。通过数组、链表和红黑树的组合,HashMap实现了高效的键值对存储与检索。文章还介绍了HashMap在不同版本中的优化,帮助读者更好地理解和应用这一重要工具。
29 5
|
16天前
|
消息中间件 架构师 Java
阿里面试:秒杀的分布式事务, 是如何设计的?
在40岁老架构师尼恩的读者交流群中,近期有小伙伴在面试阿里、滴滴、极兔等一线互联网企业时,遇到了许多关于分布式事务的重要面试题。为了帮助大家更好地应对这些面试题,尼恩进行了系统化的梳理,详细介绍了Seata和RocketMQ事务消息的结合,以及如何实现强弱结合型事务。文章还提供了分布式事务的标准面试答案,并推荐了《尼恩Java面试宝典PDF》等资源,帮助大家在面试中脱颖而出。
|
19天前
|
SQL 关系型数据库 MySQL
阿里面试:MYSQL 事务ACID,底层原理是什么? 具体是如何实现的?
尼恩,一位40岁的资深架构师,通过其丰富的经验和深厚的技術功底,为众多读者提供了宝贵的面试指导和技术分享。在他的读者交流群中,许多小伙伴获得了来自一线互联网企业的面试机会,并成功应对了诸如事务ACID特性实现、MVCC等相关面试题。尼恩特别整理了这些常见面试题的系统化解答,形成了《MVCC 学习圣经:一次穿透MYSQL MVCC》PDF文档,旨在帮助大家在面试中展示出扎实的技术功底,提高面试成功率。此外,他还编写了《尼恩Java面试宝典》等资料,涵盖了大量面试题和答案,帮助读者全面提升技术面试的表现。这些资料不仅内容详实,而且持续更新,是求职者备战技术面试的宝贵资源。
阿里面试:MYSQL 事务ACID,底层原理是什么? 具体是如何实现的?
|
19天前
|
Kubernetes 架构师 算法
阿里面试:全国14亿人,统计出重名最多的前100个姓名
文章介绍了如何解决“从全国14亿人的数据中统计出重名人数最多的前100位姓名”的面试题,详细分析了多种数据结构的优缺点,最终推荐使用前缀树(Trie)+小顶堆的组合。文章还提供了具体的Java代码实现,并讨论了在内存受限情况下的解决方案,强调了TOP N问题的典型解题思路。最后,鼓励读者通过系统化学习《尼恩Java面试宝典》提升面试技巧。
阿里面试:全国14亿人,统计出重名最多的前100个姓名
|
20天前
|
存储 安全 数据库
除了 HashMap,还有哪些数据结构可以实现键值对存储?
【10月更文挑战第11天】 除了`HashMap`,其他常见支持键值对存储的数据结构包括:`TreeMap`(基于红黑树,键有序)、`LinkedHashMap`(保留插入顺序)、`HashTable`(线程安全)、`B-Tree`和`B+Tree`(高效存储大量数据)、`SkipList`(通过跳跃指针提高查找效率)及`UnorderedMap`(类似`HashMap`)。选择合适的数据结构需根据排序、并发、存储和查找性能等需求。
|
7天前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet