zatsu na benkyou matome saito

勉強したことをまとめるだけのサイト、数学、プログラミング、機械学習とか

データ構造とアルゴリズム:ハッシュテーブル(Hash)

スクリーンショット 2020-12-20 14.13.03.png (292.2 kB)

実装

import hashlib

class HashTable(object):
    from typing import Any
    def __init__(self, size=10):
        super().__init__()
        self.size = size
        self.table = [[] for _ in range(self.size)]

    def hash(self, key) -> int:
        # hashlib.md5で文字列をエンコードしてから、文字列なので16進数のint型に直す。
        # それをhashのサイズで割った時のあまりを取得してくる。
        return int(hashlib.md5(key.encode()).hexdigest(), base=16) % self.size

    def add(self, key, value) -> None:
        index = self.hash(key)
        for data in self.table[index]:
            if data[0] == key:
                data[1] = value
                break
        else:
            self.table[index].append([key, value])

    def print(self) -> None:
        for index in range(self.size):
            print(index, end=' ')
            for data in self.table[index]:
                print('-->', end=' ')
                print(data, end=' ')
            print()

    def get(self, key) -> Any:
        index = self.hash(key)
        for data in self.table[index]:
            if data[0] == key:
                return data[1]

    def __setitem__(self, key, value) -> None:
        self.add(key, value)

    def __getitem__(self, key) -> Any:
        return self.get(key)

if __name__ == '__main__':
    hash_table = HashTable()
    hash_table['car'] = 'Tesla'
    hash_table['pc'] = 'Mac'
    hash_table['sns'] = 'YouTube'
    hash_table.print()
    print(hash_table['car'])
    # print(hash_table.table)


====== output ======
0 
1 
2 
3 
4 --> ['pc', 'Mac'] --> ['sns', 'YouTube'] 
5 --> ['car', 'Tesla'] 
6 
7 
8 
9 
Tesla

解説:

参考: ハッシュテーブル(Hash Table)を簡単に理解しよう

追加と呼び出しが早い

ハッシュテーブルも配列系のデータ構造の一種類として、他の二つは配列とリンクリストになる。 ・配列は値を呼び出す時アドレスさえあれば一瞬で終わるが、一つの値を追加・削除すると、他の値も詰めてきて、引っ越さないといけない ・リンクリストは追加が早いが(最後尾に入るから)、呼び出す時入ってるデータを一つづつ確認しないといけない ・ハッシュテーブルは、追加する時ハッシュ関数を回してキーからアドレスを得て、他の値に影響しない上で、呼び出す時キーさえあれば、アドレスもキーからわかってきて、すぐ値を尋ねられる。

解説

それぞれのkey, valueのkeyから一意の数値を計算してそれをそのkey, vlaueのアドレスとする。 そのアドレスの配列の場所にそれらの値を入れる。 今回の場合だと、

int(hashlib.md5(key.encode()).hexdigest(), base=16) % self.size

という計算式で一意の値を出力している。

>>> hashlib.md5('car'.encode()).hexdigest()
'e6d96502596d7e7887b76646c5f615d9'

この部分でcarという文字列をエンコードして一意の文字列として出力する。

その後、以下のようにint形に直す。 文字列は16進数なのでbase=16として文字列を数値にエンコードする。 この際に一つの文字列からは同じ数値しか返ってこない。

>>> int(hashlib.md5('car'.encode()).hexdigest(), base=16)
306851216158335538240511469114392712665
>>> int(hashlib.md5('car'.encode()).hexdigest(), base=16)
306851216158335538240511469114392712665
>>> int(hashlib.md5('car'.encode()).hexdigest(), base=16)
306851216158335538240511469114392712665

最後に上記の数値を配列のサイズで割り算した余剰を出力する。 理由としては、10の要素を持つ配列の場合、その配列のサイズである10で割り算することにより0 ~ 9までの数値しか余剰として出力されないため、そのアドレスを決めるときに配列の数以上になることを防げる。 もし、余剰が11などの配列の数以上になってしまうと、そのサイズの配列ではないためエラーになる。

>>> int(hashlib.md5('pc'.encode()).hexdigest(), base=16) % 10
4

getメソッド

def get(self, key) -> Any:
    index = self.hash(key)
    for data in self.table[index]:
        if data[0] == key:
            return data[1]

単純にfor文でtableをどんどん見ていって、keyが一致する場所のvlaueを出力している。 (計算量とか考えると他にも良い方法があるのかな?)

pythonと同様に実装

 def __setitem__(self, key, value) -> None:
        self.add(key, value)

    def __getitem__(self, key) -> Any:
        return self.get(key)

この部分はそれぞれ、以下のようにすると__setitem__が呼び出され hash_table['sns'] = 'YouTube'

このようにすると、getterである__getitem__が呼び出される。 print(hash_table['car'])

クイズ:足し合わせて同じになるペアを探す

① Input: [11, 2, 5, 9, 10, 3], 12 => Output: (2, 10) or None

  1. Input: [11, 2, 5, 9, 10, 3], 12 => Output: (2, 10) or None
  2. Input: [11, 2, 5, 9, 10, 3] => Output: (11, 9) or None ex) 11 + 9 = 2 + 5 + 10 + 3 のようにアウトプットを出す

set型: Pythonのset型とは、集合を扱うための型です。 もっとも普及しているリスト型のように、set型も同じく複数の値を格納できる型です。 しかし、リスト型との決定的な違いは ・重複した要素がない ・要素に順番がない といった二点が挙げられます。

【Python入門】すぐわかる!set型(集合型)の基本まとめ

from typing import  List, Tuple, Optional

def get_pair(numbers: List[int], target: int) -> Optional[Tuple[int, int]]:
    cache = set()
    # ユニークな数値のみを入れる
    for num in numbers:
        cache.add(num)
        val = target - num
        if val in cache:
            return val, num

if __name__ == '__main__':
    l = [11, 2, 5, 9, 10, 3]
    # l = [11, 2]
    t = 12
    print(get_pair(l, t))
    
===== output =====
(2, 10)

set関数は上記で説明がある通り、重複のない配列。 重複のない配列を作る過程で、ひとつづつ既存の配列からcacheのなかに数値を入れていく過程で、その追加される通知とtargetの数値を引いた値が配列の中にすでにある場合はreuturn vel, numで数値を返して終了。まだない場合は次に進むという感じ。

今回の場合は、

(1)
cache = [11]
val = 12 - 11 = 1
1はないので次に進む

(2)
cache = [11, 2]
val = 12 - 2 = 10
10はないので次に進む

(3)
cache = [11, 2, 5]
val = 12 - 5 = 7
7はcacheにないので次に進む

(4)
cache = [11, 2, 5, 9]
val = 12 - 9 = 3
3はcacheにないので次に進む

(5)
cache = [11, 2, 5, 9, 10]
val = 12 - 10 = 2
2が配列内にあるので終了。
2, 10を返す。

という流れで見つけることができる。

② Input: [11, 2, 5, 9, 10, 3] => Output: (11, 9) or None ex) 11 + 9 = 2 + 5 + 10 + 3

・リストの中で左辺 = 右辺を確立させられるような組み合わせを見つけてくる

まず、全ての要素を足算してそれを2で割ったときに余剰があるようだとこれは確立できないので終了。 2で割ったときに割り切れるようであれば、答えがあるのでこれをhalf_sum = int(sum_numbers / 2)としてhalf_sumに入れてあげる。 残りはhalf_sumをターゲットとして、ひとつ前のクイズでやったようにval = half_sum - numにvalを入れてそれぞれ追加される要素がcacheの中にあるかどうかを見て、割り切れるのであればそれが答えなので出力する。それ以外の残りの配列内の要素で今出力した和のを構築できるので答えが出る。 (残りの要素は出ない)

def get_pair_half_sum(numbers: List[int]) -> Optional[Tuple[int, int]]:
    sum_numbers = sum(numbers)
    # if sum_numbers % 2 != 0:
    #   return
    # half_sum = int(sum_numbers / 2)
    half_sum, remainder = divmod(sum_numbers, 2)
    if remainder != 0:
        return

    cache = set()
    for num in numbers:
        cache.add(num)
        val = half_sum - num
        if val in cache:
            return val, num
            
if __name__ == '__main__':
    l = [11, 2, 5, 9, 10, 3]
    # l = [11, 2]
    t = 12
    print(get_pair(l, t))

    l = [11, 2, 5, 9, 10, 3]
    print(get_pair_half_sum(l))

===== output =====
(11, 9)

クイズ実装

from typing import  List, Tuple, Optional

def get_pair(numbers: List[int], target: int) -> Optional[Tuple[int, int]]:
    cache = set()
    # ユニークな数値のみを入れる
    for num in numbers:
        cache.add(num)
        val = target - num
        if val in cache:
            return val, num

def get_pair_half_sum(numbers: List[int]) -> Optional[Tuple[int, int]]:
    sum_numbers = sum(numbers)
    # if sum_numbers % 2 != 0:
    #   return
    # half_sum = int(sum_numbers / 2)
    half_sum, remainder = divmod(sum_numbers, 2)
    if remainder != 0:
        return

    cache = set()
    for num in numbers:
        cache.add(num)
        val = half_sum - num
        if val in cache:
            return val, num

if __name__ == '__main__':
    l = [11, 2, 5, 9, 10, 3]
    # l = [11, 2]
    t = 12
    print(get_pair(l, t))

    l = [11, 2, 5, 9, 10, 3]
    print(get_pair_half_sum(l))