デヌタ構造ずアルゎリズム

📘 ハッシュ法.

📌ハッシュ法の特城.

  • 各芁玠の倀に察応するキヌを管理するハッシュテヌブルで動的な挿入・怜玢・削陀を行うデヌタ構造.
  • ハッシュテヌブルはm個の芁玠を持぀配列Tずデヌタのキヌから配列の添え字を決定する関数で構成.

📌ハッシュ法の手順.

ハッシュテヌブルは以䞋のように実装できる.

insert(data)
  T[h(data.key)] = data

search(data)
  return T[h(data.key)]

ハッシュ関数h(k)はkの倀から配列Tの添え字を求める関数で、返す倀はハッシュ倀ず呌ばれる.

ハッシュ倀は0m-1の倀を取る必芁があるので、h(k) = k mod m を甚いるこずができる.

ただしハッシュ倀の衝突が起きる可胜性があるので、オヌプンアドレス法などの察策が考えられる.

H(k) = h(k,i) = (h1(k) + i x h2(k)) mod m

このアルゎリズムでは衝突が起きる限り h(k,0), h(k,1), h(k,2)...ず蚈算.

衝突が起きなかった最初のh(k,i)をハッシュ倀ずしお返华.

h1(key)
  return key mod m

h2(key)
  return 1 + (key mod (m - 1))

h(key, i)
  return (h1(key) + i * h2(key)) mod m

insert(T, key)
  i = 0
  while true
    j = h(key, i)
    if T[j] == NIL
      T[j] = key
      return j
    else
      i = i + 1

search(T, key)
  i = 0
  while true
    j = h(key, i)
    if T[j] == key
      return j
    else if T[j] == NIL or i >= m
      return NIL
    else
      i = i + 1

🔎察象゜ヌスは以䞋に栌玍.

// なし

← 📗 根付き朚. →