배열에서 HashMap까지의 알고리즘 설명

1. 배열이란 무엇입니까?

"모든 데이터 구조는 배열의 진화이다"라는 문장을 어느 책에서 본 적이 있는지 잊어버렸습니다. 컴퓨터의 메모리는 실제로 선형 저장 공간이기 때문에 생각해보면 실제로 의미가 있습니다.

Java 샘플 코드: int[] array = new int[5]

객체 헤더 정보와 배열 길이 정보를 무시하고 JVM은 실행 시 힙에 20바이트의 메모리 공간을 할당합니다. 이는 다음과 같습니다.

​

이러한 데이터 구조는 배열 첨자를 통해 쉽게 데이터에 접근할 수 있지만 검색 시 배열을 순회해야 하며 평균 시간 복잡도는 O(n/2)입니다.

데이터의 양이 많거나 검색 작업이 빈번한 경우 이러한 순회 작업은 거의 허용되지 않습니다. 그렇다면 어떻게 하면 더 짧은 시간에 빠르게 데이터를 찾을 수 있을까요?

2. 바이너리 검색

배열의 요소가 정렬된 경우 자연스러운 방법은 이진 검색을 사용하는 것입니다.

예를 들어 길이가 1000인 정수 배열이 있습니다. 배열의 정수는 작은 것부터 큰 것 순으로 정렬됩니다. 이 배열에 6000이 있는지 알고 싶습니다. 그런 다음 먼저 배열[500]의 숫자가 6000인지 확인할 수 있습니다. 배열[500]의 숫자가 6000보다 작은 경우 배열[750]의 위치에 있는 숫자를 확인하고... 그런 다음 계속합니다. 최대 10회까지 결과를 확인할 수 있습니다.

이 알고리즘의 시간 복잡도는 O(logN)입니다.

그러나 대부분의 경우 배열 요소는 순서가 지정되지 않으며 정렬에 필요한 시간 복잡도 O(NlogN)는 일반적으로 순회에 필요한 시간을 훨씬 초과합니다.

그렇다면 문제는 다시 원점으로 돌아간 셈이다. 무질서한 데이터에서 데이터를 빠르게 찾는 방법은 무엇입니까?

3. 무지한 생각

프로그래밍을 처음 배웠을 때 "Programming Pearls"를 읽었던 기억이 납니다. 1970년대에 Mike Lesk가 전화 회사의 전화번호 검색 기능을 만들었습니다. 예를 들어 해당하는 숫자 키 5375*6*을 입력하세요. LESK*M*으로 올바른 전화번호 또는 옵션 목록을 반환할 수 있으며, 허위 일치율은 0.2%에 불과합니다.

어떻게 할 수 있나요?

그 당시 저는 데이터 구조와 알고리즘을 전혀 이해하지 못했습니다. 당시의 엉뚱한 사고 과정을 복원하는 것은 여전히 ​​​​매우 흥미 롭습니다.

㈠ 추가

모든 숫자를 더하면(* 키는 11) 5375*6*의 합은 48입니다. 대부분의 입력값의 합이 100을 넘지 않는데, 이는 배열의 처음 100개 위치에 수만 개의 전화번호가 군집된다는 것을 의미하므로 실현 가능하지 않습니다.

㈡ 곱셈

모든 숫자를 곱하면 381150이 됩니다. 이는 가능해 보이지만 문제가 있습니다. lesk, lsek, slke...의 곱이 동일하고 각 숫자 키도 3글자에 해당하므로 반복 확률이 매우 높다는 것입니다.

㈢ 곱셈 개선

① 문자는 같지만 알파벳 순서가 다른 문자열은 각 숫자에 먼저 일련번호를 곱한 다음 다른 값을 곱하는 방식으로 충돌을 피할 수 있습니다.

②각 숫자키는 영문 3자리에 해당합니다. 숫자키에 해당 문자의 일련번호를 입력하지 않으면 더 이상 정확하게 계산할 수 없습니다. 고려할 수 있는 유일한 방향은 주어진 단어 목록을 기반으로 확률 통계를 작성하는 것이므로 고려하지 않을 것입니다.

㈣ 위치 충돌

향상된 곱셈을 사용하더라도 다른 이름 문자로 계산된 곱이 계속 반복될 수 있습니다. 그러면 충돌이 발생하면 어떻게 해야 합니까?

시퀀스를 다음 빈 위치에 저장하시겠습니까? 생각해보면 이건 안 된다. 다음 공백 위치가 다른 문자 집합의 결과인 경우 2차 충돌이 발생합니다.

다행히도 소수가 있습니다.

소수는 1과 자기 자신으로만 나누어질 수 있으므로 위의 곱셈으로 얻은 모든 곱은 소수가 될 수 없으므로 소수 위치에 전화번호가 저장되지 않습니다.

그러므로 현재의 곱부터 오른쪽에 있는 다음 소수를 찾는다. 소수 위치가 그대로 사용된다면 계속해서 가장 가까운 다음 소수를 찾는다...

이 시점에서 문제는 해결된 것 같습니다.

사용자가 일련의 숫자를 입력하면, 수식에 따라 제품이 계산되고, 아래 첨자 위치의 전화번호가 반환됩니다. 틀리면 특정 소수가 붙은 배열 요소가 비어 있을 때까지 후속 소수를 순차적으로 검색하여 최종적으로 찾은 모든 전화번호를 반환합니다. 대부분의 경우 전화번호는 O(1) 시간 복잡도에서 찾을 수 있습니다.

㈤ 배열이 너무 크다

유일한 문제는 위의 아이디어에 따라 생성된 배열이 너무 크다는 것입니다. 이름은 10개의 문자로 구성됩니다. 각 문자에 해당하는 숫자가 9이면 최종적으로 얻어지는 결과는 대략 9의 17제곱입니다. 이는 9^17 크기의 배열을 구축하는 것을 의미하며 이는 완전히 실행 불가능합니다.

㈥나중에

배열이 너무 크다는 점을 고려하지 않더라도 당시의 프로그래밍 초보 수준에서는 그러한 프로그램을 작성할 수 없었을 것입니다.

제가 이런 사고 과정을 복원한 이유는 주체적인 사고 과정이 매우 흥미롭고 가치 있다고 생각하기 때문입니다. 사실 기존 알고리즘은 실제 프로젝트에서 단계별로 솔루션을 모색했던 거대 인물들에 의해 마침내 파생되었습니다.

따라서 공학에서 어려운 문제에 직면했을 때 기꺼이 문제를 분해하고 모든 작은 문제에 대한 해결책을 찾는다면 소위 많은 문제를 해결할 수 있습니다.

나중에 "데이터 구조 및 알고리즘 분석. Java 언어 설명"을 읽고 내 아이디어가 실제로 Open Addressing이라는 것을 깨달았습니다.

JDK의 HashMap은 별도의 연결을 사용합니다. 차이점: 충돌하는 데이터를 저장하기 위해 버킷 개념이 추가되고, 배열 크기를 줄이기 위해 나머지 작업이 수행됩니다.

이제 Java의 HashMap에 대해 이야기해 보겠습니다.

4. HashMap 구조 및 알고리즘에 대한 자세한 설명

HashMap의 본질은 여전히 ​​배열이며, 아래 표시된 구조와 유사한 가변 길이의 다차원 배열입니다.

㈠ 간략한 소개

HashMap의 배열은 연결된 목록의 헤드 노드를 저장합니다.

데이터 저장:

키의 hashCode를 계산한 다음 배열 길이로 나머지 연산을 수행하여 배열 첨자(연결된 목록의 헤드 노드)를 얻습니다.

위치가 비어 있으면 새 연결 리스트 노드를 생성하고 배열에 저장합니다.

위치가 비어 있지 않으면 연결된 목록의 각 노드가 주기적으로 비교됩니다. 이미 동일한 키를 가진 노드가 있고, 동일한 키를 가진 노드가 없으면 이전 노드를 덮어씁니다. 연결 목록의 꼬리 노드(참고: JDK1.8 소스 코드를 참조하세요. 새 노드는 JDK1.6과 같이 연결 목록의 헤드 노드가 되는 대신 항상 연결 목록의 끝에 추가됩니다.)

검색 데이터:

키의 hashCode를 계산한 다음 배열 길이로 나머지 연산을 수행하여 배열 첨자(연결된 목록의 헤드 노드)를 얻습니다. 연결된 목록이 비어 있지 않으면 첫 번째 노드를 먼저 비교합니다. 첫 번째 노드 키가 동일하면(hashCode가 동일하고 같음이 true임) 첫 번째 노드 키가 다르면 첫 번째 노드의 값이 직접 반환됩니다. , 연결된 목록의 다른 노드를 순차적으로 탐색하여 비교하고 동일한 키를 가진 값을 반환합니다. (동일한 키를 가진 노드가 없으면 null이 반환됩니다.)

연결된 목록을 도입하는 HashMap의 목적은 이전 섹션에서 설명한 중복 충돌 문제를 해결하는 것입니다.

참고:

모든 키의 해시코드가 동일하고 모두 0이라고 가정하면 0%4 = 0이므로 모든 요소는 연결리스트 0에 저장되며, 각 데이터를 저장하고 검색하려면 연결리스트 0을 순회해야 합니다. 그러면 이때 HashMap은 본질적으로 연결리스트로 변질되었으며, 시간복잡도도 설계된 O(1)에서 O(n/2)로 증가하였다.

HashMap 검색 및 저장의 시간 복잡도를 최대한 O(1)로 유지하려면 각 연결 목록에 요소를 균등하게 분산해야 합니다. 즉, 각 연결 목록은 하나의 요소만 저장합니다.

​그렇다면 영향을 미치는 요인은 무엇일까요?

첫째, 키의 해시코드는 반복될 수 없으며, 반드시 2개 이상의 요소를 저장하는 연결리스트가 있을 것입니다. 두 번째는 해시 함수 설계입니다. 단순한 나머지라면 나머지는 많이 반복됩니다. 세 번째는 배열의 용량입니다. 길이가 10인 배열에 100개의 요소를 분산시키려면 어떻게 계산하든 여러 요소를 저장하는 연결 리스트가 있게 됩니다. 목록은 10을 저장합니다.

이 세 가지 요소의 알고리즘 설계는 아래에서 자세히 소개됩니다.

㈡ 해시코드 생성

String 클래스의 hashCode 생성 코드입니다.

아아아아

String 클래스의 값은 char[]이고, char은 UTF-8 인코딩으로 변환될 수 있다. 예를 들어, 'a', 'b', 'c'의 UTF-8 인코딩은 각각 97, 98, 99입니다. 위 코드를 기반으로 수식으로 변환된 "abc"는 다음과 같습니다.

h = 31 * 0 + 97 = 97

h = 31 * 97 + 98 = 3105

h = 31 * 3105 + 99 = 96354

31은 상대적으로 소수의 크기에 적합하기 때문에 승수 인자로 사용됩니다. 값이 너무 작으면 해시 코드 계산에 포함된 항목 수가 적고 짝수이면 제품이 너무 작아집니다. , 이는 왼쪽 시프트와 동일합니다. 곱셈 오버플로로 인해 일반 비트 정보가 손실됩니다. 이 두 가지 모두 반복률이 증가하게 됩니다.

"abcabcabcabcabcabc"라는 문자열을 예로 들어 승수(<< 5와 동일)로 32를 사용하면 해당 해시코드의 각 단계에 대한 계산 결과는 다음과 같습니다.

​

위 그림과 같이 문자열 끝의 3글자마다 반복되는 해시코드가 생성됩니다. 이는 우연이 아닙니다. 다른 영문자로 바꿔도 반복하기 쉽고, 소수를 사용하면 반복 가능성이 크게 줄어듭니다. 관심이 있으신 분들은 위의 그림을 참고하여 왼쪽 쉬프트 연산을 해보시면 이것이 우연이 아니라는 것을 아실 수 있을 것입니다.

　　《Effective Java》一书中详细描述了hashcode的生成规则和注意事项，有兴趣的可以去看看。

　　从源代码的hashCode()方法可知，String类对象保存了已经计算好的hashCode，如果已经调用过hashCode()方法，那么第二次调用时不会再重新生成，而是直接返回已经计算好的hashCode。

　　String对象总是会存放到String类私有维护的常量池中，不显式使用new关键字时，如果常量池中已经有value相同的对象，那么总是会返回已有对象的引用。因此，很多情况下生成hashCode这种比较昂贵的操作实际上并不需要执行。

　　㈢ 哈希函数设计

　　现在，已经得到了重复率很低的hashCode，还有什么美中不足的地方吗？

　　⑴ 扰动函数

　　static final int hash(Object key) {
　　　　　　int h;
　　　　　　return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
　　}</p>
<p>
	　　下图还是以字符串“abcabcabcabcabc”为例，使用上面方法得到的运算过程和结果。</p>
<p style="text-align: center">
	　　<img alt="" src="https://img.php.cn/upload/article/000/000/007/93bb2b9f0ad8df57504d7398d6907036-4.png"></p>
<p>
	　　为什么要先无符号右位移16位，然后再执行异或运算？看看下图的二进制的与运算，你就会明白。</p>
<p style="text-align: center">
	　　<img alt="" src="https://img.php.cn/upload/article/000/000/007/93bb2b9f0ad8df57504d7398d6907036-5.png"></p>
<p>
	　　你会发现只要二进制数后4位不变，前面的二进制位无论如何变化都会出现相同的结果。为了防止出现这种高位变化而低位不变导致的运算结果相同的情况，因此需要将高位的变化也加入进来，而将整数的二进制位上半部与下半部进行异或操作就可以得到这个效果。</p>
<p>
	　　为什么要使用与运算？</p>
<p>
	　　因为哈希函数的计算公式就是hashCode % tableSize，当tableSize是2的n次方(n≥1)的时候，等价于hashCode & (tableSize - 1)。</p>
<p>
	　　扰动函数优化前：1954974080 % 16 = 1954974080 & (16 - 1) = 0</p>
<p>
	　　扰动函数优化后：1955003654 % 16 = 1955003654 & (16 - 1) = 6</p>
<p>
	　　这就是为什么需要增加扰动函数的原因。</p>
<h4>
	　　⑵ 源代码详解</h4>
<p>
	　　代码解释之前需要补充说明一下，jdk1.8引入了红黑树来解决大量冲突时的查找效率，所以当一个链表中的数据大到一定规模的时候，链表会转换成红黑树。因此在jdk1.8中，HashMap的查找和保存数据的最大时间复杂度实际上就是红黑树的时间复杂度O(logN)。</p>
<p>
	　　以下是HashMap中的保存数据的方法源代码，相信经过以上的描述，已经非常容易看懂这一段代码。</p>
<pre class="brush:php;toolbar:false">　　final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
　　　　Node<K,V>[] tab;　　　　//HashMap数组
　　　　Node<K,V> p;　　　　　　//初始化需要保存的数据
　　　　int n;　　　　　　　　　//数组容量
　　　　int i;　　　　　　　　　//数组下标

　　　　/* 如果数组为空或0，初始化容量为16 */
　　　　if ((tab = table) == null || (n = tab.length) == 0){
　　　　　　n = (tab = resize()).length;
　　　　}

　　　　/* 使用哈希函数获取数组位置(如果为空，保存新节点到数组) */
　　　　if ((p = tab[i = (n - 1) & hash]) == null){
　　　　　　tab[i] = newNode(hash, key, value, null);
　　　　}

　　　　/* 如果数组位置已经有值，则使用下列方式保存数据 */
　　　　else {
　　　　　　Node<K,V> e;　　　　//临时节点保存新值
　　　　　　K k;　　　　　　　　//临时变量用于比较key

　　　　　　//如果头节点与新节点的key的hash值相同 且 key的值相等，e赋值为旧节点
　　　　　　if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){
　　　　　　　　e = p;
　　　　　　}

　　　　　　//如果头节点是一个红黑树节点，那么e将保存为树节点
　　　　　　else if (p instanceof TreeNode){
　　　　　　	e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
　　　　　　}

　　　　　　//如果头节点与新节点不同，且头节点不是红黑树节点，循环比对链表的所有节点
　　　　　　else {
　　　　　　　　for (int binCount = 0; ; ++binCount) {
　　　　　　　　　　if ((e = p.next) == null) {
　　　　　　　　　　　　//如果直到链表尾未找到相同key的节点，将新结点作为最后一个节点加入到链表
　　　　　　　　　　　　p.next = newNode(hash, key, value, null);

　　　　　　　　　　　　//如果链表节点数大于等于8-1，转换成红黑树；转换成红黑树的最小节点数是8
　　　　　　　　　　　　if (binCount >= TREEIFY_THRESHOLD - 1){
　　　　　　　　　　　　　　treeifyBin(tab, hash);
　　　　　　　　　　　　}
　　　　　　　　　　　　break;
　　　　　　　　　　}
　　　　　　　　　　//如果循环过程中发现新旧key的值相同，跳转：是否覆盖旧值
　　　　　　　　　　if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
　　　　　　　　　　　　break;
　　　　　　　　　　}
　　　　　　　　　　p = e;
　　　　　　　　}
　　　　　　}

　　　　　　//是否覆盖旧值
　　　　　　if (e != null) {
　　　　　　　　V oldValue = e.value;
　　　　　　　　//如果新值不为空且（允许修改旧值 或 旧值为空），覆盖旧节点的值
　　　　　　　　if (!onlyIfAbsent || oldValue == null){
　　　　　　　　　　e.value = value; 	
　　　　　　　　}
　　　　　　　　afterNodeAccess(e);　　//回调函数，这里是空函数，但在linkedHashMap中实现了此方法
　　　　　　　　return oldValue;　　　　//返回旧值
　　　　　　}
　　　　}

　　　　//用于比较判断是否在遍历集合过程中有其它线程修改集合，详情请网上搜索fail-fast快速失败机制
　　　　++modCount;

　　　　//当key数量大于允许容量时进行扩容。允许容量在HashMap中是数组长度 * 装填因子(默认0.75)
　　　　if (++size > threshold){
　　　　	resize();
　　　　}

　　　　//回调函数，这里是空函数，但在linkedHashMap中实现了此方法
　　　　afterNodeInsertion(evict);
　　　　return null;
　　}

　　⑶ 简化后的伪代码

　　putval(key, value){
　　　　index = key.hashcode % tablesize;
　　　　if(null == table[index]){
　　　　　　table[index] = new node(key, value);
　　　　}else{
　　　　　　firstNode = table[index];
　　　　　　nextNode = firstNode.next;
　　　　　　while(nextNode.hasNextNode()){
　　　　　　　　//如果找到相同key的旧节点，覆盖旧节点
　　　　　　　　if(key == nextNode.key){
　　　　　　　　　　nextNode = new node(key, value);　　
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　　　//如果到队列末尾依然没有找到相同key的旧节点，将新结点加入到最后一个节点的末尾
　　　　　　　　if(nextNode.next == null){
　　　　　　　　　　nextNode.next = new node(key, value);
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　　　nextNode = nextNode.next;
　　　　　　}
　　　　}
　　}

　　⑷ 数组大小设计

　　代码注释中已经稍有提及，这里再分别展开讨论。

　　①数组容量选择

　　HashMap的初始容量是 1 << 4，也就是16。以后每次扩容都是size << 1，也就是扩容成原来容量的2倍。如此设计是因为 2^n-1(n≥1)的二进制表示总是为重复的1，方便进行求余运算。

　　《数据结构与算法分析.Java语言描述》一书中的建议是容量最好是质数，有助于降低冲突，但没有给出证明或实验数据。

　　质数虽然是神奇的数字，但个人感觉在这里并没有特别的用处。

　　根据公式index = hashCode % size可知，无论size是质数还是非质数，index的值区间都是0至(size-1)之间，似乎真正起决定作用的是hashCode的随机性要好。

　　这里先不下结论，待以后再写一个随机函数比较下质数和非质数重复率。

　　②装填因子

　　装填因子默认是0.75，也就是说如果数组容量为16，那么当key的数量大于12时，HashMap会进行扩容。

　　装填因子设计成0.75的目的是为了平衡时间和空间性能。过小会导致数组太过于稀疏，空间利用率不高；过大会导致冲突增大，时间复杂度会上升。

　　㈣ 关于其它

　　红黑树是在JDK 1.8中引入的，想用简单的语言来讲清楚红黑树的数据结构、增删改查操作及时间复杂度分析，这是一个复杂且艰难的任务，更适合单独来描述，因此留待以后吧。

　五　最小完美哈希函数(Minimal Perfect Hash Function, MPHF)

　　Jdk中的HashMap解决了任意数据集的时间复杂度问题，所设计的哈希函数在未知数据集的情况下有良好的表现。

　　但如果有一个已知数据集(如Java关键字集合)，如何设计一个哈希函数才能同时满足以下两方面的要求：

　　⑴ 容器容量与数据集合的大小完全一致；

⑵ 갈등이 없다.

즉, 특정 데이터 세트가 주어졌을 때 해시 함수가 컨테이너의 각 노드에 하나의 데이터 요소만 갖도록 허용하는 경우 이러한 해시 함수를 최소 완전 해시 함수라고 합니다.

최근에는 컴파일 원리를 연구하던 중에 키워드 집합의 O(1) 시간 복잡도 검색 문제를 해결하는 방법에 대해 언급했고, 최소 완전 해시 함수를 사용할 수 있다고 언급했습니다. 이런 용어를 보면 즉시 매우 좋고 고귀하다는 느낌이 듭니다.

위 내용은 배열에서 HashMap까지의 알고리즘 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!