ハッシュ

アルちゃん

関連


ハッシュ関数

何らかの（固定長とは限らない）データを固定長データに変換する。
コンピューター上の変換ならば、
入力を任意の（固定長とは限らない）ビット列とし、
出力は最終的には固定長のビット列となる。
この場合、出力のビット列は整数値と見た方が楽であろう。

ハッシュないしハッシュ値という語は、
このハッシュ関数の出力を指す。

簡単なもの

例えばC#のGetHashCodeをオーバーライドせねばならん時はデータのXORで済まされる。

    public override int GetHashCode()
    {
        return x ^ y;
    }

これはソートやサーチの時のハッシュの利用であって、
ハッシュが衝突してなければ一番早いが、
衝突したらしたで、衝突した中からソートやサーチをするという利用法。と思われる。
つまり、必ずしも一意でなくとも、それなりにバラけた値さえ返せればよいという考え方。と思われる。

暗号学的ハッシュ関数

セキュリティに関わるような厳密性を要するものら

MD5（Message Digest 5 ）
SHA-1（Secure Hash Algorithm 1）
SHA-2（Secure Hash Algorighm 2）
SHA-3（Secure Hash Algorighm 3）

完全ハッシュ

非固定長を固定長にギュっとするのであるから、
ハッシュは衝突することがある。
ハッシュの衝突が無いことが保証される場合を完全ハッシュという。

最小完全ハッシュ

ハッシュの衝突が無い、かつ出力が密で連続な単純な整数。

wikipediaより
n 個のキーに対する完全ハッシュ関数が最小 (minimal) であるとは、その値域が n 個の連続な整数（通常 0 から n-1）の場合である。

ハッシュテーブル

ChatGPT君の答え。
テストはしてません。

衝突考慮せず
Ｃの場合

#define TABLE_SIZE 100 
typedef struct { 
    int key; 
    int value; 
} Entry; 
Entry hashTable[TABLE_SIZE]; 
unsigned int hash(int key) { 
    return key % TABLE_SIZE; 
} 
void insert(int key, int value) { 
    unsigned int index = hash(key); 
    while (hashTable[index].key != 0) { 
        index = (index + 1) % TABLE_SIZE; 
    } 
    hashTable[index].key = key; 
    hashTable[index].value = value; 
} 
int lookup(int key) { 
    unsigned int index = hash(key); 
    while (hashTable[index].key != key) { 
        index = (index + 1) % TABLE_SIZE; 
    } 
    return hashTable[index].value; 
} 
void delete(int key) { 
    unsigned int index = hash(key); 
    while (hashTable[index].key != key) { 
        index = (index + 1) % TABLE_SIZE; 
    } 
    hashTable[index].key = 0; 
    hashTable[index].value = 0; 
}


衝突考慮
Javaの場合

基本は配列だが、ハッシュが衝突した時はListにAddする
これにより衝突したハッシュに関してはListが伸びる。

import java.util.ArrayList; 
import java.util.List; 
public class HashTable { 
    private static final int TABLE_SIZE = 100; 
    private class Entry { 
        int key; 
        int value; 
    }

    private List<Entry>[] hashTable;

    //コンストラクタ
    public HashTable() { 
        hashTable = new ArrayList[TABLE_SIZE]; 
        for (int i = 0; i < TABLE_SIZE; i++) { 
            hashTable[i] = new ArrayList<>(); 
        } 
    }

    private int hash(int key) { 
        return key % TABLE_SIZE; 
    } 
    public void insert(int key, int value) { 
        int index = hash(key); 
        hashTable[index].add(new Entry(){{ 
            this.key = key; 
            this.value = value; 
        }}); 
    } 
    public int lookup(int key) { 
        int index = hash(key); 
        for (Entry entry : hashTable[index]) { 
            if (entry.key == key) { 
                return entry.value; 
            } 
        } 
        return -1; 
    } 
    public void delete(int key) { 
        int index = hash(key); 
        for (int i = 0; i < hashTable[index].size(); i++) { 
            if (hashTable[index].get(i).key == key) { 
                hashTable[index].remove(i); 
                break; 
            } 
        } 
    } 
}


ChatGPTがつくったやつ


this.id = layer_${Date.now()}_${Math.random().toString(36).substr(2, 9)};

このコードは、`this.id`に一意の識別子を割り当てています。この識別子は、現在のタイムスタンプとランダムな文字列の組み合わせで構成されています。

以下はこのコードの動作の詳細です：

  1. `Date.now()`: 現在のタイムスタンプ（1970年1月1日00:00:00 UTCからのミリ秒数）を取得します。これにより、識別子の一部として現在の時間が含まれます。

  2. `Math.random().toString(36).substr(2, 9)`: ランダムな文字列を生成します。

    • `Math.random()` は0以上1未満のランダムな数値を生成します。

    • `.toString(36)` は、このランダムな数値を基数36（0-9とa-z）で文字列に変換します。

    • `.substr(2, 9)` は、変換後の文字列のうち、インデックス2から始まる9文字を取得します。インデックス2から始めるのは、文字列の先頭に `0.` が付くためです。

  3. テンプレートリテラル: 文字列リテラルの中で `${}` を使って変数を挿入しています。

    • `layer_` は固定の文字列です。

    • `${Date.now()}` は現在のタイムスタンプを挿入します。

    • `${Math.random().toString(36).substr(2, 9)}` はランダムな文字列を挿入します。

これにより、例えば `layer_1627667761234_k3q8z5l9a` のような一意のIDが生成されます。このIDは、各実行ごとに異なるため、一意性が保証されます。

一意性

このID生成の詳細について、以下に説明します。

1. `Date.now()`

`Date.now()` は、現在のタイムスタンプをミリ秒単位で返します。例えば、2024年7月15日12時34分56秒であれば、`Date.now()` は `1737022496000` のような数値を返します。これにより、IDに現在の時刻情報が含まれ、一部の一意性が確保されます。

2. `Math.random().toString(36).substr(2, 9)`

この部分は、ランダムな文字列を生成します。

  • `Math.random()` は0以上1未満のランダムな浮動小数点数を生成します。例えば、`0.123456789`.

  • `.toString(36)` は、この数値を基数36（0-9とa-z）で文字列に変換します。例えば、`0.123456789` は `0.4fzd4` のように変換されます。

  • `.substr(2, 9)` は、文字列の先頭の `0.` を除去し、その後の9文字を取得します。例えば、`4fzd4`。

このランダム文字列は、タイムスタンプと組み合わせることで、同じミリ秒内に複数のIDが生成された場合でも一意性を保ちます。

3. テンプレートリテラル

テンプレートリテラルを使用することで、上述の要素を組み合わせた一意のIDを生成します。

`layer_${Date.now()}_${Math.random().toString(36).substr(2, 9)}`

例えば、2024年7月15日12時34分56秒にこのコードが実行された場合、以下のようなIDが生成されることがあります：

layer_1737022496000_4fzd4

一意性の確保

このID生成の方法は以下の理由で一意性を確保します：

  1. タイムスタンプ: `Date.now()` により、ミリ秒単位で現在の時刻がIDに含まれるため、異なる時刻に生成されたIDは必ず異なります。

  2. ランダム性: `Math.random().toString(36).substr(2, 9)` により、同じミリ秒内で生成された場合でも異なるランダムな文字列が含まれます。

  3. 組み合わせ: タイムスタンプとランダム文字列を組み合わせることで、非常に高い確率でIDが一意になります。

この方法により、IDの重複が極めて起こりにくくなり、各実行ごとに異なる一意なIDが生成されます。

VS Codeで`substr`に横棒が入る理由は、`substr`が非推奨（deprecated）とされているからです。JavaScriptの最新仕様では、`substr`よりも`substring`や`slice`の使用が推奨されています。非推奨のメソッドには、将来的にサポートが削除される可能性があるため、開発者に対して使用を避けるように促すために横棒が表示されることがあります。

代替案

非推奨の`substr`を使わずに、同様の機能を提供する`substring`または`slice`を使う方法を示します。

`substring`を使う方法

`substring`は、開始インデックスと終了インデックスを指定して文字列の一部を抽出します。

this.id = `layer_${Date.now()}_${Math.random().toString(36).substring(2, 11)}`;

`slice`を使う方法

`slice`も同様に、開始インデックスと終了インデックスを指定して文字列の一部を抽出します。

this.id = `layer_${Date.now()}_${Math.random().toString(36).slice(2, 11)}`;

具体的な違い

  • `substr(start, length)`: 開始位置から指定された長さの文字列を返します。

  • `substring(start, end)`: 開始位置から終了位置までの文字列を返します。終了位置は含まれません。

  • `slice(start, end)`: `substring`と同様に、開始位置から終了位置までの文字列を返します。終了位置は含まれません。

どちらの方法も`substr`の代わりに使うことができ、推奨される方法です。したがって、コードを以下のように変更するのが良いでしょう：

this.id = `layer_${Date.now()}_${Math.random().toString(36).substring(2, 11)}`;

これで、非推奨の警告が表示されることなく、一意のIDを生成することができます。

この記事が気に入ったらサポートをしてみませんか？