pythonによるハッシュテーブルの実装
4982 ワード
ははは、これは私の最初のブログ園のブログです.pythonで実装したハッシュテーブルを試みたが,まず衝突を処理する方法はオープンアドレス法であり,衝突式はHi=(H(key)+1)mod m,mは表長である.
次はオープンアドレス法です.
ターゲット、入力:key/valueリスト、出力:ファスナー法を用いたハッシュテーブル
次の関数には、[key 01 val 01]、[key 02 val 01]、[key 03 val 01]、[key 01 val 02]、[key 02 val 02]、[key 02 val 02]、[key 01 val 03]、[...]というリストデータ構造が入力されます.
関数は、{key 01:[val 01,val 02,val 03,...]という辞書データ構造を返します.key02:[val01, val02...], key03:[val01, ...]}.この関数はMapReduce思想におけるReduce機能と類似している.
コードは次のとおりです.
1 #! /usr/bin/env python
2 #coding=utf-8
3 # （ ）
4
5 def ChangeKey(key, m, di):
6 key01 = (key+di) % m
7 return key01
8
9 a = raw_input("Please entry the numbers:
").split()
10 m = len(a)
11 dict01 = {}
12 for i in a:
13 key = int(i) % m
14 if "%s" % key in dict01:
15 NewKey = ChangeKey(key, m, 1)
16 while "%s" % NewKey in dict01: # dict01 key ，
17 NewKey = ChangeKey(NewKey, m, 1)
18 dict01["%s" % NewKey] = int(i)
19 else:
20 dict01["%s" % key] = int(i)
21 print dict01次はオープンアドレス法です.
ターゲット、入力:key/valueリスト、出力:ファスナー法を用いたハッシュテーブル
次の関数には、[key 01 val 01]、[key 02 val 01]、[key 03 val 01]、[key 01 val 02]、[key 02 val 02]、[key 02 val 02]、[key 01 val 03]、[...]というリストデータ構造が入力されます.
関数は、{key 01:[val 01,val 02,val 03,...]という辞書データ構造を返します.key02:[val01, val02...], key03:[val01, ...]}.この関数はMapReduce思想におけるReduce機能と類似している.
コードは次のとおりです.
def chainHash(InputList)：
res = {}
for line in InputList:
if line.split()[0] not in res:
temp = [] # ， ， ，
temp.append(line.split()[1])
res["%s" % line.split()[0]] = temp
else:
res["%s" % line.split()[0]].append(line.split()[1])
return res