Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 95 lines (85 sloc) 2.279 kb
fb1aafa first commit
Yoshinori Fukushima authored
1 #! /usr/local/bin/python
2 # -*- coding:utf-8 -*-
3
4 class HashOpenAddress:
5
6 def __init__(self,size=5):
7 self.size=size
8 self.table=[None]*size
9
10 def hash(self,k):
11 if type(k)==str:
12 return len(k)%self.size
13 else:
14 return int(k%self.size)
15
16 # search hash value for k
17 def search_hash(self,k):
18 hash=self.hash(k)
19 if self.table[hash]==k:
20 return hash
21 else:
22 #search eqaul column
23 count=0
24 while count<self.size:
25 if hash!=self.size-1:
26 hash+=1
27 else:
28 hash=0
29 if self.table[hash]==k:
30 return hash
31 else:
32 count+=1
33 if count>=self.size:
34 return None
35
36 def insert(self,k):
37 hash=self.hash(k)
38 if self.table[hash]==None or self.table[hash]=='deleted':
39 self.table[hash]=k
40 else:
41 #searching nil column
42 count=0
43 while count<self.size:
44 #rehush
45 if hash!=self.size-1:
46 hash+=1
47 else:
48 hash=0
49 if self.table[hash]==None or self.table[hash]=='deleted':
50 self.table[hash]=k
51 break
52 else:
53 count+=1
54 if count>=self.size:
55 print 'table is max,no empty colmun'
56
57 def delete(self,k):
58 hash=self.search_hash(k)
59 if hash!=None:
60 self.table[hash]='deleted'
61 else:
62 print 'no item,so cannot delete'
63
64 def search(self,k):
65 hash=self.search_hash(k)
66 if hash!=None:
67 return self.table[hash]
68 else:
69 return 'no item'
70
71 if __name__=='__main__':
72 h=HashOpenAddress()
73 print h.table
74 h.insert(1)
75 print h.table
76 h.insert(11)
77 print h.table
78 h.insert(16)
79 print h.table
80 h.insert(6)
81 print h.table
82 h.insert(21)
83 print h.table
84 h.insert(13)
85 print h.search(11)
86 h.delete(11)
87 print h.table
88 print h.search(11)
89 h.delete(16)
90 print h.table
91 h.insert(8)
92 print h.table
93 print h.search(8)
94
Something went wrong with that request. Please try again.