Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1782474
  • 博文数量: 297
  • 博客积分: 285
  • 博客等级: 二等列兵
  • 技术积分: 3006
  • 用 户 组: 普通用户
  • 注册时间: 2010-03-06 22:04
个人简介

Linuxer, ex IBMer. GNU https://hmchzb19.github.io/

文章分类

全部博文(297)

文章存档

2020年(11)

2019年(15)

2018年(43)

2017年(79)

2016年(79)

2015年(58)

2014年(1)

2013年(8)

2012年(3)

分类: Python/Ruby

2015-11-01 21:32:35

这个实现比较简单,出自Problem Solving with Algorithms and Data Structures using Python

点击(此处)折叠或打开

  1. class HashTable:
  2.     def __init__(self):
  3.         self.size=11
  4.         self.slots=[None]*self.size
  5.         self.data=[None]*self.size

  6.     def put(self,key,data):
  7.         hashvalue=self.hashfunction(key,len(self.slots))

  8.         if self.slots[hashvalue]==None:
  9.             self.slots[hashvalue]=key
  10.             self.data[hashvalue]=data
  11.         else:
  12.             if self.slots[hashvalue]==key:
  13.                 self.data[hashvalue]=data
  14.             else:
  15.                 nextslot=self.rehash(hashvalue,len(self.slots))
  16.                 while self.slots[nextslot]!=None and self.slots[nextslot]!=key:
  17.                     nextslot=self.rehash(nextslot,len(self.slots))

  18.                 if self.slots[nextslot]==None:
  19.                     self.slots[nextslot]=key
  20.                     self.data[nextslot]=data
  21.                 else:
  22.                     self.data[nextslot]=data

  23.     def hashfunction(self,key,size):
  24.         return key%size

  25.     def rehash(self,oldhash,size):
  26.         return (oldhash+1)%size

  27.     def get(self,key):
  28.         startslot=self.hashfunction(key,len(self.slots))

  29.         data=None
  30.         stop=False
  31.         found=False
  32.         position=startslot
  33.         while self.slots[position]!=None and not found and not stop:
  34.             if self.slots[position]==key:
  35.                 found=True
  36.                 data=self.data[position]
  37.             else:
  38.                 position=self.rehash(position,len(self.slots))
  39.                 if position==startslot:
  40.                     stop=True
  41.         return data

  42.     def ___getitem__(self,key):
  43.         return self.get(key)

  44.     def __setitem__(self,key,data):
  45.         self.put(key,data)
下面的例子出自Data Structures and Algorithms in python. 实现要复杂的多

点击(此处)折叠或打开

  1. from collections import MutableMapping
  2. class MapBase(MutableMapping):
  3.     #Our own abstract base class that includes a nonpublic _Item class
  4.     #--------------------nested _Item class
  5.     class _Item:
  6.         #Lightweight composite to store key-value pairs as map items
  7.         __slots__='_key','_value'

  8.         def __init__(self,k,v):
  9.             self._key=k
  10.             self._value=v

  11.         def __eq__(self,other):
  12.             return self._key==other._key #compare items based on their keys

  13.         def __ne__(self,other):
  14.             return not(self==other) #opposite of __eq__

  15.         def __lt__(self,other):
  16.             return self._key < other._key #compare items based on keys


  17. class UnsortedTableMap(MapBase):
  18.     #Map implementation using an unordered list

  19.     def __init__(self):
  20.         #create an empty map
  21.         self._table=[]

  22.     def __getitem__(self,k):
  23.         #return value associated with key k(raise KeyError if not found)
  24.         for item in self._table:
  25.             if k==item._key:
  26.                 return item._value
  27.         raise KeyError("Key Error: "+repr(k))
  28.     
  29.     def __setitem__(self,k,v):
  30.         #Assigned value v to key k,overwriting existing value is present
  31.         for item in self._table:
  32.             if k==item._key: #found a match
  33.                 item._value=v #reassign a value
  34.                 return #and quit
  35.         #did not find match for key
  36.         self._table.append(self._Item(k,v))

  37.     def __delitem__(self,k):
  38.         #Remove item associated with key k(raise KeyError if not found)
  39.         for j in range(len(self._table)):
  40.             if k==self._table[j]._key: #found a match
  41.                 self._table.pop(j) #remove
  42.                 return #and quit
  43.         raise KeyError("key Error:" +repr(k))

  44.     def __len__(self):
  45.         #return the number of items in the map
  46.         return len(self._table)
  47.     
  48.     def __iter__(self):
  49.         #genrate iteration of map's keys
  50.         for item in self._table:
  51.             yield item._key #yield the KEY


  52. class HashMapBase(MapBase):
  53.     #Abstract base class for map uing hash-table with MAD compression

  54.     def __init__(self,cap=11,p=109345121):
  55.         #Create an empty hash-table map
  56.         self._table=cap*[None]
  57.         self._n=0 #number of entries in the map
  58.         self._prime=p #prime for MAD compression
  59.         self._scale=1+randrange(p-1) #scale from 1 to p-1 for MAD
  60.         self._shift=randrange(p) #shift from 0 to p-1 for MAD

  61.     def _hash_function(self,k):
  62.         return (hash(k)*self._scale +self._shift)%self._prime%len(self._table)

  63.     def __len__(self):
  64.         return self._n

  65.     def __getitem__(self,k):
  66.         j=self._hash_function(k)
  67.         return self._bucket_getitem(j,k) #may raise KeyError

  68.     def __setitem__(self,k,v):
  69.         j=self._hash_function(k)
  70.         self._bucket_setitem(j,k,v) #subroutine maintains self._n
  71.         if self._n > len(self._table) // 2: #keep load factor <= 0.5
  72.             self._resize(2*len(self._table)-1) #number 2^x-1 is often prime

  73.     def __delitem__(self,k):
  74.         j=self._hash_function(k)
  75.         self._bucket_delitem(j,k) #may raise KeyError
  76.         self._n-=1

  77.     def _resize(self,c): #resize bucket array to capacity c
  78.         old=list(self.items()) #use iteration to record existing items
  79.         self._table=c*[None] #then reset table to desired capacity
  80.         self._n=0 #n recomputed during subsequent adds
  81.         for(k,v) in old:
  82.             self[k]=v #reinsert old key-value pair


  83. class ChainHashMap(HashMapBase):
  84.     #Hash map implemented with separate chaining for collision resolution

  85.     def _bucket_getitem(self,j,k):
  86.         bucket=self._table[j]
  87.         if bucket is not None:
  88.             raise KeyError('key Error: '+repr(k)) #no match found
  89.         return bucket[k] #may riase KeyError
  90.     
  91.     def _bucket_setitem(self,j,k,v):
  92.         if self._table[j] is None:
  93.             self._table[j]=UnsortedTableMap() #bucket is new to the table
  94.         oldsize=len(self._table[j])
  95.         self._table[j][k]=v
  96.         if len(self._table[j]) > oldsize: #key was new to the table
  97.             self._n+=1 #increase overall map size

  98.     def _bucket_delitem(self,k):
  99.         bucket=self._table[j]
  100.         if bucket is None:
  101.             raise KeyError('key Error: '+repr(k)) #no match found
  102.         del bucket[k] #may raise KeyError

  103.     def __iter__(self):
  104.         for bucket in self._table:
  105.             if bucket is not None: #a nonempty slot
  106.                 for key in bucket:
  107.                     yield key

  108. class ProbeHashMap(HashMapBase):
  109.     #Hash map implemented with linear probing for collision resolution
  110.     _AVAIL=object() #sentinal marks locations of previous deletions

  111.     def _is_available(self,j):
  112.         #return True if index j is available in table
  113.         return self._table[j] is none or self._table[j] is ProbeHashMap._AVAIL

  114.     def _find_slot(self,j,k):
  115.         #search for key k in bucket at index j
  116.         #return (success,index) tuple,described as follows
  117.         #if match was found,success is True and index denotes its location
  118.         #if no match found,success is False and index denotes first
  119.         #available slot
  120.         firstAvail=None
  121.         while True:
  122.             if self._is_available(j):
  123.                 if firstAvail is None:
  124.                     firstAvail=j #mark this as first avail
  125.                 if self._table[j] is NOne:
  126.                     return (False,firstAvail) #search has failed
  127.             elif k==self._table[j]._key:
  128.                 return(True,j) #found a match
  129.             j=(j+1)%len(self._table) #keep looking

  130.     def _bucket_getitem(self,j,k):
  131.         found,s=self._find_slot(j,k)
  132.         if not found:
  133.             raise KeyError('key Error:'+repr(k)) #no match found
  134.         return self._table[s]._value

  135.     def _bucket_setitem(self,j,k,v):
  136.         found,s=self._find_slot(j,k)
  137.         if not found:
  138.             self._table[s]=self._Item(k,v) #insert new item
  139.             self._n+=1 #size has increased
  140.         else:
  141.             self._table[s]._value=v #overwrite existing

  142.     def _bucket_delitem(self,j,k):
  143.         found,s=self._find_slot(j,k)
  144.         if not found:
  145.             raise KeyError('Key Error: '+repr(k)) #no match found
  146.         self._table[s]=ProbeHashMap._AVAIL #mark as vacated

  147.     def __iter__(self):
  148.         for j in range(len(self._table)): #scan entire table
  149.             if not self._is_available(j):
  150.                 yield self._table[j]._key

SortedTableMap

点击(此处)折叠或打开

  1. class SortedTableMap(MapBase):
  2.     #Map implemented using a sorted table
  3.     #-------------nonpublic behaviors--------------------
  4.     def _find_index(self,k,low,high):
  5.         #return index of the leftmost item with key greater or equal to k
  6.         #return high+1 if no such item qualifies
  7.         #that is ,j will be returned such that:
  8.         #all items of slice table[low:] have key <k
  9.         #all items of slice table[j:high+1] have key >=k

  10.         if high <low:
  11.             return high+1 #no element qualifies
  12.         else:
  13.             mid=(low+high)//2
  14.             if k==self._table[mid]._key:
  15.                 return mid #found exact match
  16.             elif k< self._table[mid]._key:
  17.                 return self._find_index(k,low,mid-1) #None: may return mid
  18.             else:
  19.                 return self._find_index(k,mid+1,high) #answer is right of mid

  20.     #--------------public behaviors-------------------------
  21.     def __init__(self):
  22.         #create an empty map
  23.         self._table=[]

  24.     def __len__(self):
  25.         #return number of items in the map
  26.         return len(self._table)

  27.     def __getitem__(self,k):
  28.         #return value associated with key k(raise KeyError if not found)
  29.         j=self._find_index(k,0,len(self._table)-1)
  30.         if j==len(self._table) or self._table[j]._key!=k:
  31.             raise KeyError('KeyError: '+repr(k))
  32.         return self._table[j]._value

  33.     def __setitem__(self,k,v):
  34.         #Assigned value v to key k,overwriting existing value if present
  35.         j=self._find_index(k,0,len(self._table)-1)
  36.         if j< len(self._table) and self._table[j]._key==k:
  37.             self._table[j]._value=v #reassign value
  38.         else:
  39.             self._table.insert(j,self._Item(k,v)) #adds new item

  40.     def __delitem__(self,k):
  41.         #Remove item associated with key k(rais KeyError if not found)
  42.         j=self._find_index(k,0,len(self._table)-1)
  43.         if j==len(self._table) or self._table[j]._key!=k:
  44.             raise KeyError('Key Error'+repr(k))
  45.         self._table.pop(j) #delete item
  46.     
  47.     def __iter__(self):
  48.         #generate keys of the map ordered from minimum to maximum
  49.         for item in self._table:
  50.             yield item._key

  51.     def __reversed__(self):
  52.         #generate key of the map ordered from maximum to minimum
  53.         for item in reversed(self._table):
  54.             yield item._key

  55.     def find_min(self):
  56.         #return (key,value) pair with minimum key(or None if empty)
  57.         if len(self._table) > 0:
  58.             return (self._table[0]._key ,self._table[0]._value)
  59.         else:
  60.             return None

  61.     def find_max(self):
  62.         #return (key,value) pair with maximum key(or None if emtpy)
  63.         if len(self._table)>0:
  64.             return (self._table[0]._key,self._table[0]._value)
  65.         else:
  66.             return None

  67.     def find_ge(self,k):
  68.         #return (key,value) pair with least key greater than or equal to k
  69.         j=self._find_index(k,0,len(self._table)-1)
  70.         if j < len(self._table):
  71.             return (self._table[j]._key,self._table[j]._value)
  72.         else:
  73.             return None

  74.     def find_lt(self,k):
  75.         #return (key,value) pair with greatest key strictly less than k
  76.         j=self._find_index(k,0,len(self.table)-1) #j's key >=k
  77.         if j>0:
  78.             return (self._table[j-1]._key,self._table[j-1]._value) #Note use of j-1
  79.         else:
  80.             return None

  81.     def find_gt(self,k):
  82.         #return (key,value) pair with least key strictly greater than k
  83.         j=self._find_index(k,0,len(self._table)-1) #j's key >= k
  84.         if j<len(self._table) and self._table[j]._key ==k:
  85.             j+=1 #advanced past match
  86.         if j < len(self._table):
  87.             return (self._table[j]._key,self._table[j]._value)
  88.         else:
  89.             return None

  90.     def find_range(self,start,stop):
  91.         #Iterate all(key,value) pairs such that start <= key <stop
  92.         #if start is None, iteration begins with minimum key of map
  93.         #if stop is None,iteration continues through the maximum key of map
  94.         if start is None:
  95.             j=0
  96.         else:
  97.             j=self._find_index(start,0,len(self._table)-1) #find first result
  98.         while j< len(self._table) and (stop is None or self._table[j]._key < stop):
  99.             yield (self._table[j]._key,self._table[j]._value)
  100.             j+=1



阅读(2331) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~