python的hashtable实现

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

class HashTable:
    def __init__(self):
        self.size=11
        self.slots=[None]*self.size
        self.data=[None]*self.size

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

        if self.slots[hashvalue]==None:
            self.slots[hashvalue]=key
            self.data[hashvalue]=data
        else:
            if self.slots[hashvalue]==key:
                self.data[hashvalue]=data
            else:
                nextslot=self.rehash(hashvalue,len(self.slots))
                while self.slots[nextslot]!=None and self.slots[nextslot]!=key:
                    nextslot=self.rehash(nextslot,len(self.slots))

                if self.slots[nextslot]==None:
                    self.slots[nextslot]=key
                    self.data[nextslot]=data
                else:
                    self.data[nextslot]=data

    def hashfunction(self,key,size):
        return key%size

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

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

        data=None
        stop=False
        found=False
        position=startslot
        while self.slots[position]!=None and not found and not stop:
            if self.slots[position]==key:
                found=True
                data=self.data[position]
            else:
                position=self.rehash(position,len(self.slots))
                if position==startslot:
                    stop=True
        return data

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

    def __setitem__(self,key,data):
        self.put(key,data)

下面的例子出自Data Structures and Algorithms in python. 实现要复杂的多

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

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

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

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

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


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

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

    def __getitem__(self,k):
        #return value associated with key k(raise KeyError if not found)
        for item in self._table:
            if k==item._key:
                return item._value
        raise KeyError("Key Error: "+repr(k))

    def __setitem__(self,k,v):
        #Assigned value v to key k,overwriting existing value is present
        for item in self._table:
            if k==item._key: #found a match
                item._value=v           #reassign a value
                return #and quit
        #did not find match for key
        self._table.append(self._Item(k,v))

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

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

    def __iter__(self):
        #genrate iteration of map's keys
        for item in self._table:
            yield item._key         #yield the KEY


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

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

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

    def __len__(self):
        return self._n

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

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

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

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


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

    def _bucket_getitem(self,j,k):
        bucket=self._table[j]
        if bucket is not None:
            raise KeyError('key Error: '+repr(k))       #no match found
        return bucket[k]                                #may riase KeyError

    def _bucket_setitem(self,j,k,v):
        if self._table[j] is None:
            self._table[j]=UnsortedTableMap()           #bucket is new to the table
        oldsize=len(self._table[j])
        self._table[j][k]=v
        if len(self._table[j]) > oldsize:               #key was new to the table
            self._n+=1                                  #increase overall map size

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

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

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

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

    def _find_slot(self,j,k):
        #search for key k in bucket at index j
        #return (success,index) tuple,described as follows
        #if match was found,success is True and index denotes its location
        #if no match found,success is False and index denotes first
        #available slot
        firstAvail=None
        while True:
            if self._is_available(j):
                if firstAvail is None:
                    firstAvail=j        #mark this as first avail
                if self._table[j] is NOne:
                    return (False,firstAvail)   #search has failed
            elif k==self._table[j]._key:
                return(True,j)                  #found a match
            j=(j+1)%len(self._table)            #keep looking

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

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

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

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

SortedTableMap

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

        if high <low:
            return high+1                           #no element qualifies
        else:
            mid=(low+high)//2
            if k==self._table[mid]._key:
                return mid                          #found exact match
            elif k< self._table[mid]._key:
                return self._find_index(k,low,mid-1) #None: may return mid
            else:
                return self._find_index(k,mid+1,high) #answer is right of mid

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

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

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

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

    def __delitem__(self,k):
        #Remove item associated with key k(rais KeyError if not found)
        j=self._find_index(k,0,len(self._table)-1)
        if j==len(self._table) or self._table[j]._key!=k:
            raise KeyError('Key Error'+repr(k))
        self._table.pop(j) #delete item

    def __iter__(self):
        #generate keys of the map ordered from minimum to maximum
        for item in self._table:
            yield item._key

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

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

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

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

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

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

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