JavaScriptの一般的なアルゴリズムとデータ構造

JavaScriptのデータ構造について話をするとき、我々はこの言語の最も重要な構造-過去を得ることができません.それがフードの下で何を持っているか、そして、なぜハッシュアルゴリズムが必要であるかについて見ましょう.

連想配列

JavaScript objects are an example of an associative array. Unlike regular arrays, associative arrays do not have indexes, but rather keys (usually strings). Otherwise, there is almost no difference – the keys are unique and each corresponds to a certain value. Associative arrays are also called dictionaries or maps (from the English map). They allow you to conveniently represent complex data of various types (for example, user information) and are very popular in JavaScript programming.

効率的には連想配列は他のデータ構造より優れている.たとえば、単純な配列の真ん中に新しい要素を追加するには、再インデックスを付けなければなりません(最初の部分ではこの話をしました).この演算の複雑さはo(n)である.連想配列では、単に値が関連付けられている新しいキーを追加します.

ハッシュテーブル
しかし、連想配列は独自の弱さを持っています.通常のインデックス配列とは異なり、コンピュータのメモリに格納できません.連想配列を格納するために、特別な構造が使われます--ハッシュテーブル(ハッシュマップ).
連想配列はシンタックスシュガー、ハッシュテーブルへのより便利なアドオンです.

ハッシュテーブル操作の概略図

ハッシュ
連想配列のキーを通常のインデックスのインデックスにするには、2つの操作を実行する必要があります.

ハッシュ(ハッシュキー)を見つける

見つかったハッシュを結果の配列のインデックスに変換する.

すなわち、最終的なタスクは、キーを数値インデックスに変換することであるが、通常は2段階で実行される.

ハッシュの計算
ハッシュ関数は入力データを受け取り、それを固定長のハッシュ文字列または数値に変換します.おそらく、いくつかのハッシュアルゴリズムについて聞いたことがあります.キーは、ハッシュ関数が扱うことができるどんなデータ型でも表すことができます.
gitにおけるコミットのハッシュIDの例.変更を保存するとき、それらはハッシュされます、そして、あなたは0481e0692e2501192d67d7da506c6e70ba41e913のような何かを得ます.これはあなたの変更のために計算されたハッシュです.
ハッシュ関数の実装は非常に異なることができます.たとえば、最も単純なID関数を使用することができます.この関数は、入力パラメータを受け取り、そのまま変更します.

const hash = key => key;

キーが文字列の場合、すべての文字のコードの合計を計算できます.

const hash = string => {
    let result = 0;
    for (let i = 0; i < string.length; i++) {
        result += string.charCodeAt(i);
    }
    return result;
};

例えば、キーのハッシュ値は417で、キーの年齢のハッシュ値は301です.
これらのすべては、ハッシュ関数の非常に良い例ではありません、彼らは通常実生活でより複雑です、しかし、我々が一般原則を理解することは重要です.ハッシュテーブルがどのようなデータを扱うのかを知っていれば、一般的な場合よりも特定のハッシュ関数を選択できます.
重要:同じ入力値の場合、ハッシュ関数は常に同じ結果を返します.

インデックスへのキャスティング
通常、結果の配列のサイズはすぐに決定されるので、インデックスは指定した範囲内になければなりません.ハッシュは通常インデックスより大きいので、さらに変換する必要があります.
インデックスを計算するには、配列のサイズでハッシュを分割する剰余を使用できます.

const index = Math.abs(hash) % 5;

配列が長いほど、メモリにかかるスペースが増えることを覚えておくことが重要です.
ハッシュ関数を使用し、連想配列を通常の配列に変換します.

// associative array
const user = {
  name: 'John',
  age: 23
};

// default array, length = 5
[
    undefined,
    ['age', 23],
    ['name', 'John'],
    undefined,
    undefined
]

キー名はインデックス2に対応し、キーの年齢はインデックス1に対応する.
結果の配列だけでなく、元のキーに値を格納します.これがなぜ必要なのか、すぐにわかる.
今、キー名を持つ配列要素を取得したい場合は、このキーをハッシュして、連想配列の要素がどのインデックスにあるかを確認する必要があります.

衝突
あなたは既にそのような変換の弱点を見ますか?

The key in an associative array can be absolutely any string of any length – the number of options is infinite. And the number of indexes in the array is limited. In other words, there are not enough indexes for all keys, and for some input data, the hash function will return the same result. This is called a collision.

衝突を解決する2つの一般的な方法があります.

オープンアドレッシング
ハッシュ関数を連想配列(Key 1)のキーの一部として渡し、このキーに対応する正規配列の2つのインデックスから受け取ります.

[ undefined, undefined, [key1, value1], undefined, undefined, undefined, undefined ]

それから、我々はもう一つのキー- Key 2を通過します、そして、再び、我々は2を得ます－衝突がありました.私たちは同じインデックスの下で新しいデータを書くことができません.これを線形プロービングと呼ぶ.2 - 3以降の次のインデックスは無料です.

[ undefined, undefined, [key1, value1], [key2, value2], undefined, undefined, undefined ]

第3のキーKit 3のために、ハッシュ関数はインデックス3を返します、しかし、それはすでにキーKey 2によって占領されます.

[ undefined, undefined,  [key1, value1], [key2, value2], [key3,value3], undefined, undefined ]

レコードは明確ですが、キーのようなハッシュテーブル、例えばKit 3で希望のキーを見つけることができますか?同様に、まずハッシュ関数を実行し、3を取得します.このインデックスで配列要素をチェックし、これが我々が探しているキーではないことを確認します.ですから、ソースキーをハッシュテーブルに格納しているので、見つかった要素が正確に必要なものであることを確認できます.我々は、配列を通してさらに動き始めます.そして、各々の要素を繰り返して、我々が探しているキーと比較します.
ハッシュテーブルがより密に設定されている場合、より多くの反復を行う必要があります.

チェーン法
このアプローチでは、単一のインデックスに対応する値がリンクリストとして格納されます.配列の各インデックスは1つの要素ではなく、ハッシュ関数が1つのインデックスを計算した要素のリストに対応します.衝突が起こるならば、新しい要素は単にリストの終わりに加えられます.

そのようなハッシュテーブルに特定のキーを持つ要素を検索するとき、まず、ハッシュを計算し、目的の配列インデックスを決定し、希望するキーを見つけるまでリスト全体を調べます.
この実装では、テーブルから項目を削除することができます.リンクリストでは、削除操作は一定時間かかります.

JavaScriptのハッシュテーブルの実装
ハッシュテーブルは連想配列インターフェースを実装しなければなりません.
新しいキー値組を加えることキーによる値のための

検索;

キーでペアを削除します.

ハッシュテーブルサイズ(配列長)が小さいほど、頻繁に衝突する.例として、32を少々取る.実際には、プライム番号(1つだけで分割可能です)はハッシュ表のサイズにしばしば使用されます.これは、衝突が少ないと仮定する.
衝突を解決するために、チェーンメソッドを使用します.これを行うには、リンクリストクラスLinkedListが必要です.

const hashTableSize = 32;

class HashTable {
  constructor() {
    this.buckets = Array(hashTableSize).fill(null);
  }

  hash(key) {
    let hash = Array.from(key).reduce((sum, key) => {
      return sum + key.charCodeAt(0);
    }, 0);
    return hash % hashTableSize;
  }

  set(key, value) {
    // calculating the hash for the key
    let index = this.hash(key);

    // create if there is no list for this hash yet
    if (!this.buckets[index]) {
      this.buckets[index] = new LinkedList();
    }

    let list = this.buckets[index];
    // check if the key was added earlier
    let node = list.find((nodeValue) => {
      nodeValue.key === key;
    });

    if (node) {
      node.value.value = value; // updating the value for the key
    } else {
      list.append({ key, value }); // adding a new item to the end of the list
    }
  }

  get(key) {
    // calculating the hash for the key
    let index = this.hash(key);
    // we find the corresponding list in the array
    let list = this.buckets[index];

    if (!list) return undefined;

    // we are looking for an item with the desired key in the list
    let node = list.find((nodeValue) => {
      return nodeValue.key === key;
    });

    if (node) return node.value.value;
    return undefined;
  }

  delete(key) {
    let index = this.hash(key);
    let list = this.buckets[index];

    if (!list) return;

    let node = list.find((nodeValue) => nodeValue.key === key);
    if (!node) return;

    list.delete(node.value);
  }
}

ハッシュ表における基本演算の効率
ハッシュテーブルの主な操作は次の2つの段階からなります.

キーのハッシュを計算し、結果の配列でこのハッシュに対応する要素をチェックします.

あなたがすぐに正しいものを見つけなかったならば、

は他の要素を通して繰り返します.

最初のステージは常に一定の時間、2番目の-線形、すなわち、ソートする必要がある要素の数に依存します.
ハッシュテーブルの有効性は、次の3つの主要な要因に依存します.

キーのインデックスを計算するハッシュ関数.理想的には、それは配列全体に均等にインデックスを分配するべきです

テーブル自体のサイズ-それが大きいほど、より少ない衝突があります;

衝突解決方法.例えば、連鎖法は、一定の時間に新しい要素を加える操作を減らす.

最後に、より少ない衝突では、より効率的なテーブルが動作します.なぜなら、検索がハッシュですぐに見つからなかった場合、多くの要素を反復処理する必要はないからです.一般に、ハッシュテーブルは他のデータ構造よりも効率的です.

ハッシュテーブルの使用

Hash tables are widely used in programming, for example, for authorization mechanisms, indexing large amounts of information (databases), caching, or searching. Another common case is the implementation of unordered sets, which we will discuss in the next part of the cycle.

JavaScriptでは、純粋な形式のハッシュテーブルはほとんど使用されません.通常、すべての作業は正常なオブジェクト(連想配列)またはより複雑なマップによって正常に実行されます.同時に、より低いレベル(プログラム解釈)で、ハッシュテーブルはオブジェクトを表すのに用いられます.
様々な動作を最適化するとき、オブジェクトとハッシュテーブルはしばしば補助構造として使われます.たとえば、文字列内のさまざまな文字の出現回数をカウントします.

function countSymbols(string) {
    const hash = {};
    [...string].forEach(s => {
    let symbol = s.toLowerCase();
    if (!(symbol in hash)) hash[symbol] = 0;
    hash[symbol]++;
  });
  return hash;
}

countSymbols('Hello, world!');
/*
{ " ": 1, "!": 1, ",": 1, d: 1, e: 1, h: 1, l: 3, o: 2, r: 1, w: 1 }
*/

ハッシュ、符号化、暗号化

Hashing is an algorithm that works only in one direction. It is impossible to get the original value from the hash, and there is no practical need for this, because the main task of hashing is to distinguish input data, not to save it.

場合によっては、双方向の変換が必要です.たとえば、他の誰も読むことができない友人に秘密のメッセージを残したい.これは、暗号化アルゴリズムが救助に来るところです.

You convert the source text to some other sequence of characters using a cipher. Such a sequence is either completely unreadable (just a set of letters), or it has a completely different meaning. If someone intercepts this email, they simply won't understand what you were trying to say. Your friend knows that the message is encrypted and knows how to decrypt it. Thus, the main purpose of encryption is to hide information from unauthorized persons. To do this, use a secret key or even two keys – one for encryption, the second for decryption.

暗号化に加えて、エンコーディングもあります.それは本質的に暗号化に近いですが、目的の異なる.符号化は、情報の伝送を簡素化するために使用され、例えば、電気通信回線を超えている.あなたのメッセージは、一連のビットに変換されて、ワイヤーの上に受取人に届けられて、もう一方の端で再び回復しました.この場合、キーは使用されません.このようなコードは、通信の問題を解決するだけでなく、送信中に可能な干渉に対処しようとする場合もある.最も有名なコードの一つは、モールス符号です.

結論
ハッシュテーブルを扱っている間、私たちはもう一度プログラミングのほとんどすべてが行われることを確認しました.配列.したがって、フードの下の連想オブジェクトはまた、ハッシュ関数を使用して各キーのインデックスを計算し、それらを使用します.