hashmap原理 hashmap的底层数据结构

一、java面试都问知不知道hashmap的原理，那我就想问，知道原理有什么用

Java中的HashMap可以说是平时开发中最常用的数据结构之一了，经常使用的集合类还有ArrayList、HashSet，基本上用好HashMap、ArrayList、HashSet这三大集合类，大多数的业务场景就满足了，掌握这三大集合类也是作为一名Java程序员的基础能力。

平时开发大多数的业务场景都是CRUD，且数据量都很小，所以基本上不会有什么问题。那么还需要知道其底层实现原理吗？还需要知道这些集合类的数据结构吗？

当然需要，这很重要！这里就拿HashMap来具体说一说了解它的设计思想多么的重要！

HashMap的底层数据结构简单来说就是数组+链表+红黑树，这个大家都知道，面试也是高频面试题，用一张图来形容就是：

那这个时候你就得知道数组的好处了，基于下标的随机访问和赋值数组元素的时间复杂度都是O(1)，这就能保证HashMap数据没有哈希冲突的时候它的set/put方法都是O(1)的，这也是HashMap要追求的极致目标（尽管会有哈希冲突）。这就是HashMap查询性能快、插入数据快的主要原因，是一个空间换时间的思想。

但前提是我们得知道我们要把一个数据插入到数组的哪个下标，因此就采用了哈希的思想。一个对象一定有一个唯一的hash值，但是两个对象也有可能有相同的hash值，这叫“哈希冲突”。所以为了更好的利用数组，哈希值计算要尽可能的避免冲突，也就是追求“低碰撞率”。

这也涉及到另外一个问题，比较一个对象的时候为什么要重写它的hashcode()方法和equals()方法。

那业内除了Java自带的Hashcode()方法还有哪些hash算法你了解吗？比如MurmurHash算法。他们都在哪些开源软件中应用到？各种哈希算法的性能比较又如何？我们平时开发能不能借鉴这种思想？

当哈希冲突的时候，HashMap就会使用到链表，即数组+链表，那你知道数组和链表的区别吗？LinkedHashMap和HashMap的区别呢？都适合在哪些场景用到？如果让你手写一个LRU缓存，你会怎么写？

你可能想说我不需要知道数组和链表的数据结构，我也没有手写LRU缓存的场景，我只想做一条安静的咸鱼，简简单单CRUD就好。

大家都说平时开发都是CRUD，那你知道如何把CRUD写的高大上一点吗？比如其中的C（查询）应该是最为频繁的。学过数据结构的都知道，高效查找主要的两种算法：有序查找（二分）和哈希查找。HashMap的数组就是用到了哈希查找，时间复杂度是O(1)，那么你理解了HashMap的原理是不是就基本掌握了哈希查找算法的原理？另外当哈希冲突导致链表节点数量达到8时候，就会变成红黑树，红黑树就是有序查找的变种。如果你又进一步掌握了红黑树的查找原理，是不是就基本掌握了有序查找算法的原理？所以HashMap的原理重不重要？掌握了HashMap的原理是不是就掌握了高效查找的方法？如果你没掌握这些原理，你觉得掌握了没有用，但是当你掌握了，在日常业务开发中你会发现受用无穷。

HashMap中还有很多思想值得大家学习，掌握这些思想后，其实才是你编程能力的质的提升。手里有武器不用和手里没有武器不是一回事。

二、为什么面试要问hashmap的原理

面试官问HashMap的原理可能只是在考察你是否有专研学习的精神，因为HashMap是用的最多的，如果你连HashMap的原理都不知道，面试官大概就可以定义你对任何东西都是只会用，但是不知道其原理。现在都会用的人那么多，为什么要选你了？所以这个问题可能是筛选的一个条件。

当然，主要应该还是知道原理才能更好的使用和解决问题，这才是最重要的。

三、hashmap的put方法的原理

HashMap的put方法的原理主要基于哈希表（HashTable）的数据结构。在HashMap中，键值对是通过键的哈希码来定位到具体的存储位置，然后将键值对存入该位置。

具体来说，当调用put方法时，会执行以下步骤：

1.**计算键的哈希码**：HashMap使用键的哈希函数来计算键的哈希码。哈希码是一种基于键的值，它能够唯一标识一个键。通过哈希函数，可以将键转换成哈希码，使得不同的键具有不同的哈希码，从而能够将键值对存储在不同的位置。

2.**定位存储位置**：根据键的哈希码，HashMap会使用链表（或红黑树）等数据结构来存储键值对。通过哈希码，可以快速定位到存储位置。

3.**插入键值对**：将键值对插入到存储位置中。如果该位置已经存在键相同的值，则会根据HashMap的策略（例如使用红黑树）来进行合并或覆盖。

4.**返回旧值**：如果键不存在于HashMap中，则将新的键值对插入并返回null；如果键已经存在，则返回旧的值。

值得注意的是，由于HashMap允许有相同的键存在，因此可能会发生键值对的更新或覆盖操作。同时，HashMap还提供了快速查找和访问的能力，使得在大量数据中查找或修改键值对变得非常高效。

以上就是HashMap的put方法的原理。在实际使用中，需要注意HashMap的容量和负载因子等参数，以适应不同场景的需求。