iframe-proxy | Sunbelt Computer Software

54 lines (45 loc) · 1.79 KB

MAP Abstract Data Type
Map() Create a new, empty map. It returns an empty map collection.
put(key,val) Add a new key-value pair to the map. If the key is already in the map then replace the old value with the new value.
get(key) Given a key, return the value stored in the map or None otherwise.
del Delete the key-value pair from the map using a statement of the form del map[key].
len() Return the number of key-value pairs stored in the map.
in Return True for a statement of the form key in map, if the given key is in the map, False otherwise.
class HashTable(object):
    def __init__(self, size = 11):
        self.size = size
        self.keys = [None] * size # keys
        self.values = [None] * size # values
    def put(self, key, value):
        hashval = self.hash(key)
        if hashval not in keys:
            self.keys[hashval] = key
            self.values[hashval] = value
        else:
            if self.keys[hashval] == key: # replace
                self.values[hashval] = value
            else: # probing
                rehashval = self.rehash(key)
                while self.keys[rehashval] is not None and \
                        self.keys[rehashval] != key:
                    rehashval = self.rehash(rehashval)
                if keys[rehashval] is None:
                    self.keys[rehashval] = key
                    self.values[rehashval] = value
                else:
                    self.values[rehashval] = value # replacee
    def get(self, key):
        pass
    def hash(self, key):
        return key % self.size
    def rehash(self, oldhash):
        """
        linear probing
        """
        return (oldhash + 1) % self.size
    def __getitem__(self,key):
        return self.get(key)
    def __setitem__(self, key, value):
        self.put(key, value)

Sunbelt Computer Software

PL/B Language Development and Support

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

hashtable.py

Latest commit

History

hashtable.py

File metadata and controls