配列から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 年代にマイク・レスクが電話会社の電話番号検索機能を構築しました。たとえば、5375*6* に対応する数字キーを入力します。 LESK*M* に対して、正しい電話番号またはオプションのリストが返される可能性がありますが、誤一致率はわずか 0.2% です。

どうすればそれができるのでしょうか？

当時はデータ構造もアルゴリズムも全く理解していなかったので、当時の妄想のプロセスを復元するのは今でも非常に興味深いです。

㈠追加

すべての数値を加算すると (* キーは 11)、5375*6* の合計は 48 になります。ほとんどの入力の合計は 100 を超えません。これは、数万の電話番号が配列の最初の 100 の位置にクラスター化されることを意味するため、現実的ではありません。

㈡掛け算

すべての数値を掛け合わせると、積は 381150 になります。これは実現可能に思えますが、問題があります。lesk、lsek、slke... の積は同じであり、各数字キーも 3 つの文字に対応しているため、反復される可能性が非常に高くなります。

㈢ 乗算の改善

① 同じ文字を含むがアルファベット順が異なる文字列は、この方法で競合を回避できます。各数値は最初にシリアル番号で乗算され、次に他の値で乗算されます。

②各数字キーは 3 つの英字に対応しています。ユーザーが数字キーに文字のシーケンス番号を入力しないと、それ以上正確に計算することはできません。与えられた単語リストに基づいて確率統計を行うという方向性しか考えられないので考慮しない。

㈣ 場所の競合

改良された乗算を使用したとしても、異なる名前文字で計算された積が繰り返される可能性があります。では、競合が発生した場合はどうすればよいでしょうか。

シーケンスを次の空の場所に保存しますか?考えてみれば、これはうまくいきません。次の空白位置が別の文字セットの積である場合、二次的な競合が発生します。

幸いなことに、素数は存在します。

素数は 1 とそれ自体でしか割り切れないため、上記の乗算で得られる積は素数になることができないため、電話番号は素数の位置に格納されません。

したがって、現在の積から始めて、右隣の素数を検索します。素数の位置がまだ使用されている場合は、次に近い素数の検索を続けます...

この時点で、問題は解決されたように見えます。

ユーザーが数字の文字列を入力すると、式に従って積が計算され、下付き文字の位置にある電話番号が返されます。間違っている場合は、ある素数で添字が付いた配列要素が空になるまで後続の素数を順番に検索し、最終的に見つかったすべての電話番号を返します。ほとんどの場合、電話番号は O(1) 時間の計算量で見つけることができます。

㈤ 配列が大きすぎます

唯一の問題は、上記の考え方に従って作成された配列が大きすぎることです。名前は 10 文字あり、各文字に対応する数字が 9 である場合、最終的に得られる積は約 9 の 17 乗になります。これは、サイズ 9^17 の配列を構築することを意味しますが、これは完全に不可能です。

㈥あとで

配列が大きすぎるという要因を考慮に入れなかったとしても、当時の私のプログラミング初心者レベルでは、このようなプログラムは作成できませんでした。

私がこの思考プロセスを復元した理由は、独立した思考プロセスが非常に興味深く価値があると考えたからです。考えてみてください。実際、既存のアルゴリズムは、実際のプロジェクトで段階的に解決策を模索した偉人たちによって最終的に導き出されたものです。

したがって、エンジニアリングでいくつかの難しい問題に遭遇したとき、問題を分解して考え、あらゆる小さな問題の解決策を模索する意欲があれば、いわゆる問題の多くは解決できます。

その後、「データ構造とアルゴリズムの分析。Java 言語の説明」を読んだ後、自分のアイデアが実際にはオープン アドレッシングであることに気づきました。

JDK の HashMap は個別のチェーンを使用します。違い: 競合するデータを保存するためにバケットの概念が追加され、配列サイズを削減するために剰余演算が実行されます。

それでは、Java の HashMap について話しましょう。

4. HashMapの構造とアルゴリズムの詳細説明

HashMap の本質はやはり配列であり、以下に示す構造に似た可変長の多次元配列です。

㈠簡単な紹介

HashMap の配列には、リンク リストのヘッド ノードが格納されます。

セーブデータ:

キーの hashCode を計算し、配列の長さで剰余演算を実行して配列の添字 (リンク リストの先頭ノード) を取得します。

位置が空の場合は、新しいリンク リスト ノードを生成し、配列に保存します。

位置が空でない場合、リンクされたリスト内の各ノードが循環的に比較されます。同じキーを持つノードがすでに存在し、同じキーを持つノードがない場合は古いノードが上書きされ、新しいノードが次のように使用されます。リンク リストの末尾ノード (注: JDK1.8 ソース コードを参照してください。新しいノードは、JDK1.6 のようにリンク リストの先頭ノードではなく、常にリンク リストの末尾に追加されます)。

データの検索:

キーの hashCode を計算し、配列の長さで剰余演算を実行して配列の添字 (リンク リストの先頭ノード) を取得します。リンクされたリストが空でない場合は、最初のノードを比較します。最初のノード キーが同じである場合 (hashCode が同じで、等しい場合)、最初のノード キーが異なる場合は、最初のノードの値が直接返されます。 、リンクされたリスト内の他のノードが順番に走査されて比較され、同じキーを持つノードの値が返されます (同じキーを持つノードが見つからない場合は null が返されます)。

HashMap にリンク リストを導入する目的は、前のセクションで説明した重複競合の問題を解決することです。

注:

すべてのキーのハッシュコードが同じ場合、すべて 0 であると仮定すると、0%4 = 0 となり、すべての要素はリンク リスト 0 に保存され、各データの保存と検索にはリンク リスト 0 を走査する必要があります。そして、この時点の HashMap は実質的に連結リストに縮退しており、時間計算量も設計上の O(1) から O(n/2) に増加しています。

HashMap の検索と保存の時間の複雑さを可能な限り O(1) に保つために、要素は各リンク リストに均等に分散される必要があります。つまり、各リンク リストは 1 つの要素のみを保存します。

では、影響を与える要因は何でしょうか?

まず、キーのハッシュコードを繰り返すことはできません。繰り返した場合、少なくとも 2 つの要素を保存するためのリンクされたリストが必ず存在します。 2 つ目はハッシュ関数の設計です。単純な剰余の場合、剰余は何度も繰り返されます。 3 つ目は、配列の容量です。100 個の要素が長さ 10 の配列に分散される場合、どのように計算しても、複数の要素を保存するためのリンクされたリストが存在することになります。リストは 10 個保存されます

これら 3 つの要素のアルゴリズム設計については、以下で詳しく紹介します。

㈡ ハッシュコード生成

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 は素数の比較的適切なサイズであるため、乗数として使用されます。値が小さすぎると、ハッシュコードの計算に必要な項目の数が少ない場合に積が小さくなりすぎます。偶数の場合は、31 が乗数として使用されます。 、乗算オーバーフローによって通常のビット情報が失われる場合、これは左シフトに相当します。これらは両方ともリピート率の向上につながります。

乗数として 32 を使用した場合 (<< 5 に相当)、文字列「abcabcabcabcabc」を例にとると、そのハッシュコードの各ステップの計算結果は次のようになります。

上の図に示すように、文字列の末尾の 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关键字集合)，如何设计一个哈希函数才能同时满足以下两方面的要求：

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

⑵ 矛盾はありません。

言い換えれば、あるデータセットが与えられたとき、ハッシュ関数によってコンテナの各ノードがデータ要素を 1 つだけ持つことができる場合、そのようなハッシュ関数は最小完全ハッシュ関数と呼ばれます。

最近、私はコンパイルの原理を勉強していて、キーワード セットの O(1) 時間計算量検索問題を解決する方法について言及し、最小の完全ハッシュ関数が使用できることについて言及しました。このような言葉を見ると、すぐにとても良い気持ちになり、崇高な気持ちになります。

以上が配列からHashMapまでのアルゴリズム解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。