Shulou(Shulou.com)06/01 Report--

This article mainly explains "what are the uses of java hashing algorithm". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "what are the uses of java hashing algorithm"?

What is a hash?

Hash, refers to the process of turning arbitrary length input into fixed length output through a certain algorithm, this output is called hash value, or hash code, this algorithm is called Hash algorithm, or Hash function, this process is generally called Hash, or computing Hash,Hash is translated into Chinese hash, hash, hash and so on.

Since it is a fixed-length output, it means that the input is infinite and the output is limited, so it is inevitable that different inputs may get the same output. Therefore, the Hash algorithm is generally irreversible.

So what is the use of the Hash algorithm?

The use of hash algorithm

Hash algorithm is a generalized algorithm, or an idea, it does not have a fixed formula, as long as it satisfies the algorithm defined above, it can be called Hash algorithm.

Generally speaking, it has the following uses:

Encrypt the password, for example, using MD5+ salt to encrypt the password

Quick query, for example, the use of hash table, through the hash table can quickly query elements

Digital signatures, such as inter-system calls plus signatures, can prevent tampering with data

File inspection, for example, there is usually an MD5 value when downloading Tencent Games. After downloading the installation package, a MD5 value is calculated and compared with the official MD5 value, you can know whether the file has been damaged or tampered with in the download process.

Well, speaking of the Hash algorithm, or the Hash function, in Java, the parent class Object of all objects has a Hash function, the hashCode () method, so why do you need to define such a method in the Object class?

> strictly speaking, there is a difference between the Hash algorithm and the Hash function. I believe you can distinguish it according to the context.

Let's see what the comments on the JDK source code say:

Return a hash value for this object that exists to better support hash tables, such as HashMap. To put it simply, this method is for hash tables such as HashMap.

/ / the internal address of the object public native int hashCode () is returned by default.

At this point, we have to mention another method in the Object class-- equals ().

/ / the default is to directly compare whether the addresses of two objects are equal public boolean equals (Object obj) {return (this = = obj);}

What kind of entanglement do hashCode () and equals have?

Generally speaking, hashCode () can be seen as a weak comparison, returning to the nature of Hash, mapping different inputs to fixed-length outputs, then the following situations occur:

If the input is the same, the output must be the same

If the input is different, the output may be the same or different.

The output is the same, the input may be the same, or different

If the output is different, the input must be different.

Equals () is a strict way to compare whether two objects are equal, so if two objects equals () is true, then their hashCode () must be equal, what if they are not equal?

If equals () returns true and hashCode () is not equal, then if you think of these two objects as key of HashMap, they will most likely be positioned in different slots of HashMap, and there will be a HashMap with two equal objects inserted, which is not allowed, which is why if you override the equals () method, you must override the hashCode () method.

For example, for the class String, we all know that its equals () method compares whether the contents of two strings are equal, not the addresses of two strings. Here is its equals () method:

Public boolean equals (Object anObject) {if (this = = anObject) {return true;} if (anObject instanceof String) {String anotherString = (String) anObject; int n = value.length; if (n = = anotherString.value.length) {char v1 [] = value; char v2 [] = anotherString.value; int I = 0 While (n return true; -! = 0) {if (v1 [I]! = v2 [I]) return false; iTunes;} return true;}} return false;}

So, for the following two string objects, using equals () to compare them is equal, but their memory addresses are not the same:

String a = new String; String b = new String; System.out.println (a.equals (b)); / / trueSystem.out.println (a = = b); / / false

At this point, if the hashCode () method is not overridden, then an and b will return different hash codes, which will cause great interference to the key where we often use String as HashMap, so the hashCode () method that String overrides:

Public int hashCode () {int h = hash; if (h = = 0 & & value.length > 0) {char val [] = value; for (int I = 0; I

< value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h;} 这个算法也很简单，用公式来表示为：s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]。 好了，既然这里屡次提到哈希表，那我们就来看看哈希表是如何一步步进化的。 哈希表进化史数组 讲哈希表之前，我们先来看看数据结构的鼻祖--数组。 数组比较简单，我就不多说了，大家都会都懂，见下图。 数组的下标一般从0开始，依次往后存储元素，查找指定元素也是一样，只能从头（或从尾）依次查找元素。 比如，要查找4这个元素，从头开始查找的话需要查找3次。 早期的哈希表 上面讲了数组的缺点，查找某个元素只能从头或者从尾依次查找元素，直到匹配为止，它的均衡时间复杂是O(n)。 那么，利用数组有没有什么方法可以快速的查找元素呢？ 聪明的程序员哥哥们想到一种方法，通过哈希函数计算元素的值，用这个值确定元素在数组中的位置，这样时间复杂度就能缩短到O(1)了。 比如，有5个元素分别为3、5、4、1，把它们放入到数组之前先通过哈希函数计算位置，精确放置，而不是像简单数组那样依次放置元素（基于索引而不是元素值来查找位置）。 假如，这里申请的数组长度为8，我们可以造这么一个哈希函数为hash(x) = x % 8，那么最后的元素就变成了下图这样： 这时候我们再查找4这个元素，先算一下它的hash值为hash(4) = 4 % 8 = 4，所以直接返回4号位置的元素就可以了。 进化的哈希表 事情看着挺完美，但是，来了一个元素13，要插入的哈希表中，算了一下它的hash值为hash(13) = 13 % 8 = 5，纳尼，它计算的位置也是5，可是5号已经被人先一步占领了，怎么办呢？ 这就是哈希冲突。 为什么会出现哈希冲突呢？ 因为我们申请的数组是有限长度的，把无限的数字映射到有限的数组上早晚会出现冲突，即多个元素映射到同一个位置上。 好吧，既然出现了哈希冲突，那么我们就要解决它，必须干！ How to？ 线性探测法 既然5号位置已经有主了，那我元素13认怂，我往后挪一位，我到6号位置去，这就是线性探测法，当出现冲突的时候依次往后挪直到找到空位置为止。 然鹅，又来了个新元素12，算得其hash值为hash(12) = 12 % 8 = 4，What？按照这种方式，要往后移3次到7号位置才有空位置，这就导致了插入元素的效率很低，查找也是一样的道理，先定位的4号位置，发现不是我要找的人，再接着往后移，直到找到7号位置为止。 二次探测法 使用线性探测法有个很大的弊端，冲突的元素往往会堆积在一起，比如，12号放到7号位置，再来个14号一样冲突，接着往后再数组结尾了，再从头开始放到0号位置，你会发现冲突的元素有聚集现象，这就很不利于查找了，同样不利于插入新的元素。 这时候又有聪明的程序员哥哥提出了新的想法--二次探测法，当出现冲突时，我不是往后一位一位这样来找空位置，而是使用原来的hash值加上i的二次方来寻找，i依次从1，2，3...这样，直到找到空位置为止。 还是以上面的为例，插入12号元素，过程是这样的，本文来源于公主号彤哥读源码： 这样就能很快地找到空位置放置新元素，而且不会出现冲突元素堆积的现象。 然鹅，又来了新元素20，你瞅瞅放哪？ 发现放哪都放不进去了。 研究表明，使用二次探测法的哈希表，当放置的元素超过一半时，就会出现新元素找不到位置的情况。 所以又引出一个新的概念--扩容。 什么是扩容？ 已放置元素达到总容量的x%时，就需要扩容了，这个x%时又叫作扩容因子。 很显然，扩容因子越大越好，表明哈希表的空间利用率越高。 所以，很遗憾，二次探测法无法满足我们的目标，扩容因子太小了，只有0.5，一半的空间都是浪费的。 这时候又到了程序员哥哥们发挥他们聪明特性的时候了，经过996头脑风暴后，又想出了一种新的哈希表实现方式--链表法。 链表法 不就是解决冲突嘛！出现冲突我就不往数组中去放了，我用一个链表把同一个数组下标位置的元素连接起来，这样不就可以充分利用空间了嘛，啊哈哈哈哈~~ 嘿嘿嘿嘿，完美△△。 真的完美嘛，我是一名黑客，我一直往里面放*%8=4的元素，然后你就会发现几乎所有的元素都跑到同一个链表中去了，呵呵，最后的结果就是你的哈希表退化成了链表，查询插入元素的效率都变成了O(n)。 此时，当然有办法，扩容因子干啥滴？ 比如扩容因子设置为1，当元素个数达到8个时，扩容成两倍，一半的元素还在4号位置，一半的元素去到了12号位置，能缓解哈希表的压力。 然鹅，依旧不是很完美，也只是从一个链表变成两个链表，本文来源于公主号彤哥读源码。 聪明的程序员哥哥们这次开启了一次长大9127的头脑风暴，终于搞出了一种新的结构--链表树法。 链表树法 虽然上面的扩容在元素个数比较少的时候能解决一部分问题，整体的查找插入效率也不会太低，因为元素个数少嘛。 但是，黑客还在攻击，元素个数还在持续增加，当增加到一定程度的时候，总会导致查找插入效率特别低。 所以，换个思路，既然链表的效率低，我把它升级一下，当链表长的时候升级成红黑树怎么样？ 嗯，我看行，说干就干。 嗯，不错不错，妈妈再也不怕我遭到黑客攻击了，红黑树的查询效率为O(log n)，比链表的O(n)要高不少。 所以，到这就结束了吗？ 你想多了，每次扩容还是要移动一半的元素好么，一颗树分化成两颗树，这样真的好么好么好么？ 程序员哥哥们太难了，这次经过了12127的头脑风暴，终于想出个新玩意--一致性Hash。 一致性Hash 一致性Hash更多地是运用在分布式系统中，比如说Redis集群部署了四个节点，我们把所有的hash值定义为0~2^32个，每个节点上放置四分之一的元素。 >

Here is just an example, the principle of the actual Redis cluster is like this, the specific value is not like this.

At this point, suppose you need to add a node to Redis, such as node5, between node3 and node4, so that you only need to move the element between node3 to node4 from node4 to node5, and the other elements remain the same.

In this way, the speed of capacity expansion is increased, and fewer elements are affected, and most of the requests are almost unaware.

At this point, I believe you have a deeper understanding of "what is the use of the java hashing algorithm?" you might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.