java 散列,java散列函数

　　什么是散列表

　　哈希表也叫哈希表，是一种提供键和值的映射关系的数据结构。只要给定一个键，就能高效地找到它匹配的值，时间复杂度接近O(1)。

　　如何解决写爬虫IP受阻的问题？立即使用。

　　在线学习视频推荐：java视频

　　散列表的工作原理

　　哈希表本质上是一个数组。我们知道数组可以按照下标随机访问，比如A [0]，A [1]，A [2]，A [3]和A [4]，所以它的查询效率很高。在哈希表中，当我们给一个键时，我们可以立即查询相应的值。这时候我们就需要一个“中转站”来以某种方式转换键和数组下标，这个中转站就是hash函数。

　　哈希函数在不同语言中的实现是不同的。Java中使用HashMap。

　　在Java和大多数面向对象的语言中，每个对象都有自己的hashcode来区分不同的对象，这个hashcode是一个整数变量。此时，我们需要将这个整型变量转换成数组的下标。转换这个变量最简单的方法是对数组的长度取模。

　　公式如下：

　　index=hashcode(key)% array . length例如：

　　给定一个长度为8的数组，我们想找到key 001121 对应的值，而 001121 的hashcode是1420036703，那么我们可以先通过下面的计算得到数组下标：

　　index=HashCode(“001121”)% array . length=1420036703% 8=7散列表的读写操作

　　1.写操作

　　写就是在哈希表中插入一个新的键值对(jdk中称为Entry)。

　　具体方法是：通过hash函数将键值转换成数组下标，然后在数组中的那个位置插入条目(注意是条目键值对Key Value，而不仅仅是Value)。可想而知，不同的键值可能被转换成同一个下标，然后就变成了哈希冲突。

　　解决哈希冲突的常用方法有开放寻址法和链表法。

　　开放式寻址方法的基本思想是：当出现哈希冲突时，将条目放在下一个数组的空位置，即一个一个向后移动。

　　链表方法(应用在Java HashMap集合类中)的基本思想是数组中的每个元素既是一个Entry对象，又是一个链表的头节点。每个入口对象通过next指针指向它的下一个入口节点。当新的Entry对象映射到与之冲突的数组位置时，只需要插入到对应的链表中即可。

　　2.读操作

　　读操作对应写操作，只有冲突的情况才需要特殊处理。

　　具体思路是：通过hash函数，把要找的键值转换成数组下标，然后检查数组中这个位置的键值是否是我们要找的键；如果是，则找到它，并且可以返回该条目的值；否则，继续向下搜索链表，看是否有对应的键值。

　　举个例子，当我们想找到002936的键对应的值时，先把键转换成数组下标，得到下标2。检查完这个元素后，我们发现这个元素的键是002947，这不是我们要查询的键，于是我们继续向下搜索链表。

　　3.扩容

　　我们知道数组扩展是数组中的元素个数达到数组的最大长度，那么哈希表什么时候扩展呢？

　　当哈希表在多次元素插入后达到一定的饱和度时，哈希碰撞的概率会增加。此时大量的元素拥挤在同一个数组下标位置，对后续的插入和查询操作的性能影响很大。这时候就需要扩展哈希表了。

　　影响散列表扩容的因素为：

　　容量，即HashMap的当前长度

　　LoadFactor，也就是HashMap的加载因子，默认为0.75。

　　扩容需要满足的条件：

　　hashmap . size=capacity x load factor简单解释为：当哈希表中的条目数超过当前容量与其负载因子的乘积，并且要存储的位置中已经有元素(哈希碰撞)时，当这两个条件都满足时，就需要扩展输入容量，这样就会使原来的容量增加一倍。加载因子的默认值为0.75，这是空间和时间的折衷。加载因子过高(冲突可以存储在链表中)，降低了空间成本，但也增加了查询成本。

　　扩容的步骤：

　　扩展不是简单地扩展哈希表的长度，而是经历了以下两个步骤：

　　1.扩充容量，创建一个新的条目空数组，长度是原数组的两倍；

　　2.再次散列，遍历原始条目数组，并将所有条目散列到新数组中。

　　扩展后，原来拥挤的哈希表又变得稀疏，原来的条目尽可能均匀分布。需要注意的是，在HashMap的实现方面，JDK8与之前的版本有很大的不同。当多个条目被哈希到同一个数组下标位置时，为了提高插入和搜索的效率，HashMap会将条目的链表转换成红黑树之类的数据结构。

　　相关文章教程推荐：java语言入门以上是java中散列表详细介绍的详细内容。更多请关注我们的其他相关文章！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。