「java哈希表原理」哈希表java实现

本篇文章给大家谈谈java哈希表原理，以及哈希表java实现对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、HashMap实现原理
• 2、详解java中hashcode什么时候用，怎么用？
• 3、hashmap底层实现原理
• 4、HashMap底层实现原理剖析
• 5、HashMap详解
• 6、hashmap底层实现原理是什么？

HashMap实现原理

HashMap在实际开发中用到的频率非常高，面试中也是热点。所以决定写一篇文章进行分析，希望对想看源码的人起到一些帮助，看之前需要对链表比较熟悉。

以下都是我自己的理解，欢迎讨论，写的不好轻喷。

HashMap中的数据结构为散列表，又名哈希表。在这里我会对散列表进行一个简单的介绍，在此之前我们需要先回顾一下 数组 、 链表 的优缺点。

数组和链表的优缺点取决于他们各自在内存中存储的模式，也就是直接使用 顺序存储 或 链式存储 导致的。无论是数组还是链表，都有明显的缺点。而在实际业务中，我们想要的往往是寻址、删除、插入性能都很好的数据结构，散列表就是这样一种结构，它巧妙的结合了数组与链表的优点，并将其缺点弱化（并不是完全消除）

散列表的做法是将key映射到数组的某个下标，存取的时候通过key获取到下标（index）然后通过下标直接存取。速度极快，而将key映射到下标需要使用 散列函数 ，又名 哈希函数 。说到哈希函数可能有人已经想到了，如何将key映射到数组的下标。

图中计算下标使用到了以下两个函数：

值得注意的是，下标并不是通过hash函数直接得到的，计算下标还要对hash值做index()处理。

Ps：在散列表中，数组的格子叫做 桶 ，下标叫做 桶号 ，桶可以包含一个key-value对，为了方便理解，后文不会使用这两个名词。

以下是哈希碰撞相关的说明：

以下是下标冲突相关的说明：

很多人认为哈希值的碰撞和下标冲突是同一个东西，其实不是的，它们的正确关系是这样的， hashCode发生碰撞，则下标一定冲突；而下标冲突，hashCode并不一定碰撞

上文提到，在jdk1.8以前HashMap的实现是 散列表 = 数组 + 链表 ，但是到目前为止我们还没有看到链表起到的作用。事实上，HashMap引入链表的用意就是解决下标冲突。

下图是引入链表后的散列表：

如上图所示，左边的竖条，是一个大小为16的数组，其中存储的是链表的头结点，我们知道，拥有链表的头结点即可访问整个链表，所以认为这个数组中的每个下标都存储着一个链表。其具体做法是，如果发现下标冲突，则 后插入的节点以链表的形式追加到前一个节点的后面 。

这种使用链表解决冲突的方法叫做： 拉链法 （又叫链地址法）。HashMap使用的就是拉链法，拉链法是冲突发生以后的解决方案。

Q：有了拉链法，就不用担心发生冲突吗？

A：并不是！由于冲突的节点会不停的在链表上追加，大量的冲突会导致单个链表过长，使查询性能降低。所以一个好的散列表的实现应该从源头上减少冲突发生的可能性，冲突发生的概率和哈希函数返回值的均匀程度有直接关系，得到的哈希值越均匀，冲突发生的可能性越小。为了使哈希值更均匀，HashMap内部单独实现了hash()方法。

以上是散列表的存储结构，但是在被运用到HashMap中时还有其他需要注意的地方，这里会详细说明。

现在我们清楚了散列表的存储结构，细心的人应该已经发现了一个问题：Java中数组的长度是固定的， 无论哈希函数是否均匀，随着插入到散列表中数据的增多，在数组长度不变的情况下，链表的长度会不断增加 。这会导致链表查询性能不佳的缺点出现在散列表上，从而使散列表失去原本的意义。为了解决这个问题，HashMap引入了扩容与负载因子。

以下是和扩容相关的一些概念和解释：

Ps： 扩容要重新计算下标 ， 扩容要重新计算下标 ， 扩容要重新计算下标 ，因为下标的计算和数组长度有关，长度改变，下标也应当重新计算。

在1.8及其以上的jdk版本中，HashMap又引入了红黑树。

红黑树的引入被用于替换链表，上文说到，如果冲突过多，会导致链表过长，降低查询性能，均匀的hash函数能有效的缓解冲突过多，但是并不能完全避免。所以HashMap加入了另一种解决方案，在往链表后追加节点时，如果发现链表长度达到8，就会将链表转为红黑树，以此提升查询的性能。

详解java中hashcode什么时候用，怎么用？

有许多人学了很长时间的Java，但一直不明白hashCode方法的作用，

我来解释一下吧。首先，想要明白hashCode的作用，你必须要先知道Java中的集合。

总的来说，Java中的集合（Collection）有两类，一类是List，再有一类是Set。

你知道它们的区别吗？前者集合内的元素是有序的，元素可以重复；后者元素无序，但元素不可重复。

那么这里就有一个比较严重的问题了：要想保证元素不重复，可两个元素是否重复应该依据什么来判断呢？

这就是Object.equals方法了。但是，如果每增加一个元素就检查一次，那么当元素很多时，后添加到集合中的元素比较的次数就非常多了。

也就是说，如果集合中现在已经有1000个元素，那么第1001个元素加入集合时，它就要调用1000次equals方法。这显然会大大降低效率。

于是，Java采用了哈希表的原理。哈希（Hash）实际上是个人名，由于他提出一哈希算法的概念，所以就以他的名字命名了。

哈希算法也称为散列算法，是将数据依特定算法直接指定到一个地址上。如果详细讲解哈希算法，那需要更多的文章篇幅，我在这里就不介绍了。

初学者可以这样理解，hashCode方法实际上返回的就是对象存储的物理地址（实际可能并不是）。

这样一来，当集合要添加新的元素时，先调用这个元素的hashCode方法，就一下子能定位到它应该放置的物理位置上。

如果这个位置上没有元素，它就可以直接存储在这个位置上，不用再进行任何比较了；如果这个位置上已经有元素了，

就调用它的equals方法与新元素进行比较，相同的话就不存了，不相同就散列其它的地址。

所以这里存在一个冲突解决的问题。这样一来实际调用equals方法的次数就大大降低了，几乎只需要一两次。

所以，Java对于eqauls方法和hashCode方法是这样规定的：

1、如果两个对象相同，那么它们的hashCode值一定要相同；2、如果两个对象的hashCode相同，它们并不一定相同 上面说的对象相同指的是用eqauls方法比较。

你当然可以不按要求去做了，但你会发现，相同的对象可以出现在Set集合中。同时，增加新元素的效率会大大下降。hashcode这个方法是用来鉴定2个对象是否相等的。 那你会说，不是还有equals这个方法吗？ 不错，这2个方法都是用来判断2个对象是否相等的。但是他们是有区别的。 一般来讲，equals这个方法是给用户调用的，如果你想判断2个对象是否相等，你可以重写equals方法，然后在代码中调用，就可以判断他们是否相等 了。简单来讲，equals方法主要是用来判断从表面上看或者从内容上看，2个对象是不是相等。举个例子，有个学生类，属性只有姓名和性别，那么我们可以 认为只要姓名和性别相等，那么就说这2个对象是相等的。 hashcode方法一般用户不会去调用，比如在hashmap中，由于key是不可以重复的，他在判断key是不是重复的时候就判断了hashcode 这个方法，而且也用到了equals方法。这里不可以重复是说equals和hashcode只要有一个不等就可以了！所以简单来讲，hashcode相 当于是一个对象的编码，就好像文件中的md5，他和equals不同就在于他返回的是int型的，比较起来不直观。我们一般在覆盖equals的同时也要 覆盖hashcode，让他们的逻辑一致。举个例子，还是刚刚的例子，如果姓名和性别相等就算2个对象相等的话，那么hashcode的方法也要返回姓名 的hashcode值加上性别的hashcode值，这样从逻辑上，他们就一致了。 要从物理上判断2个对象是否相等，用==就可以了。

hashmap底层实现原理

hashmap底层实现原理是SortedMap接口能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。

如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable

从结构实现来讲，HashMap是：数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的。

扩展资料

从源码可知，HashMap类中有一个非常重要的字段，就是 Node[] table，即哈希桶数组。Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)，除了K，V，还包含hash和next。

HashMap就是使用哈希表来存储的。哈希表为解决冲突，采用链地址法来解决问题，链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。

如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。

HashMap底层实现原理剖析

Hashmap是一种非常常用的、应用广泛的数据类型，最近研究到相关的内容，就正好复习一下。网上关于hashmap的文章很多，但到底是自己学习的总结，就发出来跟大家一起分享，一起讨论。

1.HashMap的数据结构：在java 中 数据结构，最基本 也就两种 一种数组 一种模拟指针。所有的数据结构都可以用这两个基本结构来构造的，hashmap也不例外。Hashmap实际上是一个数组和链表的结合体。数组的默认长度为16，

2.hashMap源码解析

static final int DEFAULT_INITIAL_CAPACITY = 1 4; // 初始化容量大小 

static final int MAXIMUM_CAPACITY = 1 30; ///容器最大值

static final float DEFAULT_LOAD_FACTOR = 0.75f; //加载影子

static final Entry[] EMPTY_TABLE = {}; //null 的hashMap

transient Entry[] table = (Entry[]) EMPTY_TABLE;///动态扩大容器时使用的一个hashMap

transient int size;//当前数据量

int threshold;//扩大容器时的大小 为 capacity * load factor

final float loadFactor;//使用率阀值，默认为：DEFAULT_LOAD_FACTOR

存取元素 ：调用put方法

public V put(K key, V value) { 

//判断当前table 为Null 第一次Put 

 if (table == EMPTY_TABLE) {

     inflateTable(threshold);  //初始化容器的大小

 }

 if (key == null) 

 return putForNullKey(value); //判断当前key 为null 将Null key添加到数组的第一个位置

 int hash = hash(key); //将当前key进行hash 详情见下方

 int i = indexFor(hash, table.length); //调用完hash算法后，详情见下方

 for (Entry e = table[i]; e != null; e = e.next) { //循环判断当前数组下标为Entry的实体 将当前key相同的替换为最新的值

            Object k;

            if (e.hash == hash ((k = e.key) == key || key.equals(k))) {

                V oldValue = e.value;

                e.value = value;

                e.recordAccess(this);

                return oldValue;

            }

        }

        modCount++;

        addEntry(hash, key, value, i); //如果key都不同 则添加Entry.详情见下方

        return null;

    }

hashMap的hash算法剖析

final int hash(Object k) {

        int h = hashSeed;

        if (0 != h k instanceof String) {  //判断当前k是否为string 和

            return sun.misc.Hashing.stringHash32((String) k); //使用stringHash32算法得出key   的hash值

        }

        h ^= k.hashCode(); //调用key的hashCode 得出值 后使用"或"运算符 

        h ^= (h 20) ^ (h 12);

        return h ^ (h 7) ^ (h 4);

前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的 元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表，这样就大大优化了查询的效率。

一个十进制数32768(二进制1000 0000 0000 0000)，经过上述公式运算之后的结果是35080(二进制1000 1001 0000 1000)。看出来了吗？或许这样还看不出什么，再举个数字61440(二进制1111 0000 0000 0000)，运算结果是65263(二进制1111 1110 1110 1111)，现在应该很明显了，它的目的是让“1”变的均匀一点，散列的本意就是要尽量均匀分布。使用上述算法后 "1"就变得很均匀了。

我们用table[index]表示已经找到的元素需要存储的位置。先判断该位置上有没有元素（这个元素是HashMap内部定义的一个类Entity， 基本结构它包含三个类，key，value和指向下一个Entity的next）,没有的话就创建一个Entity对象，在 table[index]位置上插入，这样插入结束；如果有的话，通过链表的遍历方式去逐个遍历，看看有没有已经存在的key，有的话用新的value替 换老的value；如果没有，则在table[index]插入该Entity，把原来在table[index]位置上的Entity赋值给新的 Entity的next，这样插入结束

    }

indexFor 返回当前数组下标 ，

static int indexFor(int h, int length) {

        return h (length-1);

    }

那么得到key 之后的hash如何得到数组下标呢 ？把h与HashMap的承载量（HashMap的默认承载量length是16，可以自动变长。在构造HashMap的时候也可以指定一个长 度。这个承载量就是上图所描述的数组的长度。）进行逻辑与运算，即 h (length-1)，这样得到的结果就是一个比length小的正数，我们把这个值叫做index。其实这个index就是索引将要插入的值在数组中的 位置。第2步那个算法的意义就是希望能够得出均匀的index，这是HashTable的改进，HashTable中的算法只是把key的 hashcode与length相除取余，即hash % length，这样有可能会造成index分布不均匀。

首先来解释一下为什么数组大小为2的幂时hashmap访问的性能最高？

看下图，左边两组是数组长度为16（2的4次方），右边两组是数组长度为15。两组的hashcode均为8和9，但是很明显，当它们和1110“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hashcode的值会与14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！ 

void addEntry(int hash, K key, V value, int bucketIndex) {

  //// 若HashMap的实际大小 不小于 “阈值”，则调整HashMap的大小

        if ((size = threshold) (null != table[bucketIndex])) {

            resize(2 * table.length);

            hash = (null != key) ? hash(key) : 0;

          //// 设置“bucketIndex”位置的元素为“新Entry”，// 设置“e”为“新Entry的下一个节点”

            bucketIndex = indexFor(hash, table.length);

        }

        createEntry(hash, key, value, bucketIndex);

    }

//将当前key 和value添加到Entry[]中

void createEntry(int hash, K key, V value, int bucketIndex) { 

        Entry e = table[bucketIndex];  //将第一个就得table 复制个新的entry 

        table[bucketIndex] = new Entry(hash, key, value, e); //将当前新的Entry 复制个table[bucketIndex]  旧的table[bucketIndex] 和新的table[buckIndex]之间用next关联。第一个键值对A进来，通过计算其key的hash得到的index=0，记做:table[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做: B.next = A ,table[0] = B,如果又进来C,index也等于0,那么 C.next = B ,table[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起

        size++; //容量加1

    }

以上就是HashMap添加元素时的过程解析

那么如何get元素呢？

public V get(Object key) {

 if (key == null) return getForNullKey(); //当前key是否为null 如果为null值返回table[0]这个value

    Entry entry = getEntry(key);

        return null == entry ? null : entry.getValue();

    }

final EntrygetEntry(Object key) {

 if (size == 0) { return null; }  //判断容量是否大于0 

 int hash = (key == null) ? 0 : hash(key); //对当前key 进行hash hash后得到一个值

 for (Entry e = table[indexFor(hash, table.length)]; //获取当前Entry 循环遍历

            e != null;

            e = e.next) {

            Object k;

            if (e.hash == hash

                ((k = e.key) == key || (key != null key.equals(k))))

                return e;

        }

        return null;

    }

扩展问题:

1.当前我们的hashMap中越来越大的之后，"碰撞"就越来越明显，那么如何解决碰撞呢？扩容！

当hashmap中的元素个数超过数组大小capti*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。比如说，我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适，不过上面annegu已经说过，即使是1000，hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的，因为0.75*1000 1000, 也就是说为了让0.75 * size 1000, 我们必须这样new HashMap(2048)才最合适，既考虑了的问题，也避免了resize的问题

HashMap的两种遍历方式

第一种

Map map = newHashMap();

Iterator iter = map.entrySet().iterator();

while(iter.hasNext()) {

Map.Entry entry = (Map.Entry) iter.next();

Object key = entry.getKey();

Object val = entry.getValue();

}

效率高,以后一定要使用此种方式！

第二种

Map map = newHashMap();

Iterator iter = map.keySet().iterator();

while(iter.hasNext()) {

Object key = iter.next();

Object val = map.get(key);

}

效率低,以后尽量少使用！

归纳

简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，

也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

HashMap详解

(1)存储键值对，实现快速存取数据；

(2)允许键/值为null，但不允许重复的键；

(3)非同步synchronized(比同步快)，线程不安全；

注：让HashMap同步： Map m = Collections.synchronizeMap(hashMap);

(4)实现Map接口，对键值对进行映射，不保证有序(比如插入的顺序)

注：Map接口有两个基本的实现，HashMap和TreeMap。TreeMap保存了对象的排列次序，而HashMap则不能。

(5)HashMap默认的容量大小是16；增加容量时，每次将容量变为“原始容量x2”

(6)HashMap添加元素时，是使用自定义的哈希算法;

(1)不存储键值对，仅存储对象；

(2)不允许键/值为null；

(3)线程安全(速度慢)，采用synchronize关键字加锁原理(几乎在每个方法上都加锁)，；

(4)实现了Set接口，不允许集合中有重复的值。注：将对象存储在HashSet之前，要先确保对象重写equals()和hashCode()方法，

比较对象的值是否相等，以确保set中没有储存相等的对象。hashCode()可能相同，用equals()判断对象的相等性。

(5)Hashtable默认的容量大小是11；增加容量时，每次将容量变为“原始容量x2 + 1”；

(6)Hashtable没有自定义哈希算法，而直接采用的key的hashCode()。

(1)Java并发包java.util.concurrent中的一个线程安全且高效的HashMap实现

(2)不允许键/值为null；

(3)线程安全：在JDK1.7中采用“分段锁”的方式，1.8中直接采用了CAS（无锁算法）+ synchronized。

Entry：HashMap是一个用于存储Key-Value键值对的集合，每一个键值对叫做Entry，这些Entry分散存储在一个数组当中。

hashMap是在bucket中储存键对象和值对象，作为Map.Entry

bucket：HashMap初始化时，创建一个长度为capacity的Entry数组，这个数组里可以存储元素的位置被称为“桶(bucket)”，

每个bucket都有其指定索引，系统可以根据其索引快速访问该bucket里存储的元素。

loadFactor：负载因子。默认值DEFAULT_LOAD_FACTOR = 0.75f；

capacity：容量，指的是数组的长度

threshold：阈值=capacity*loadFactor。超过阈值则扩容为原来的两倍。

size：HashMap的大小，它是HashMap保存的键值对的数量。

HashMap是基于hashing的原理，底层使用哈希表结构(数组+链表)实现。使用put(key,value)存储对象，使用get(key)获取对象。

理解为，数组中存储的是一个Entry，并且作为链表头结点，头结点之后的每个节点中储存键值对对象Entry。

给put()方法传递键和值时，先对键调用hashCode()方法计算hash从而得到bucket位置，进一步存储，

HashMap会根据当前bucket的占用情况自动调整容量(超过负载因子Load Facotr则resize为原来的2倍)。

扩容扩的是数组的容量，发生碰撞后当链表长度到达8后，链表上升为红黑树，提高速度。

根据键key的hashcode找到bucket位置，然后遍历链表节点，调用equals(用来获取值对象)方法确定键值对，找到要找的值对象。

a.对key的hashCode做hash操作(高16bit不变，低16bit和高16bit做了一个异或)

b.计算下标(n-1) hash，从而获得buckets的位置 //h (length-1)

数字分析法、平方取中法、分段叠加法、 除留余数法、 伪随机数法。

其他解决hash冲突办法：开放定址法、链地址法、再哈希法。

根据hashcode来划分的数组，如果数组的坐标相同，则进入链表这个数据结构中，jdk1.7及以前为头插法，jdk1.8之后是尾插法，

在jdk1.8之后，当链表长度到达8的时候，jdk1.8上升为红黑树。存的时候按照上面的方式存，取的时候根据equals确定值对象。

1.常见问题：集合类、数据结构、线程安全、解决碰撞方法、hashing概念和方法、equals()和hashCode()的应用、不可变对象的好处

hashmap底层实现原理是什么？

HashMap的实现原理：首先有一个每个元素都是链表（可能表述不准确）的数组，当添加一个元素（key-value）时，就首先计算元素key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了。

这时就添加到同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，同一各链表上的Hash值是相同的，所以说数组存放的是链表。而当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率。

当链表数组的容量超过初始容量的0.75时，再散列将链表数组扩大2倍，把原链表数组的搬移到新的数组中。

HashMap 的实例有两个参数影响其性能：

初始容量和加载因子。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。

加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。在Java编程语言中，加载因子默认值为0.75，默认哈希表元为101。

java哈希表原理的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于哈希表java实现、java哈希表原理的信息别忘了在本站进行查找喔。