<jupyter_start><jupyter_text>Hash Tables<jupyter_code>class HashMap:
    def __init__(self):
        self.size = 10
        self.map = [None] * self.size
def _get_hash(self, key):
    return key % self.size

HashMap._get_hash = _get_hash
def add(self, key, value):
    key_hash = self._get_hash(key)
    key_value = [key, value]
    
    # insert or update: "upsert"
    
    self.map[key_hash] = [ key_value ] # notice the double list. we'll get to it in a minute
    return True
HashMap.add = add
def get(self, key):
    key_hash = self._get_hash(key)
    if self.map[key_hash] is not None:
        for pair in self.map[key_hash]:
            if pair[0] == key:
                return pair[1]
    
    raise KeyError(str(key))

HashMap.get = get
l = ['a', 'b', 'c']
for i, item in enumerate(l):
    print(i, "---", item)
def __str__(self):
    ret = ""
    
    for i, item in enumerate(self.map):
        if item is not None:
            ret += str(i) + ": " + str(item) + "\n"
    return ret

HashMap.__str__ = __str__
h = HashMap()

h.add(17, "seventeen")
h.add(26, "Twenty six")
h.add(35, "Thirty five")
h.add(26, "Twenty six updated")
print(h)
print(h.get(26))<jupyter_output>Twenty six updated<jupyter_text>Collision and Acoidance<jupyter_code>h = HashMap()

h.add(17, "seventeen")
h.add(26, "Twenty six")
h.add(35, "Thirty five")
h.add(26, "Twenty six updated")
h.add(887, "large number")

print(h)
def add(self, key, value):
    key_hash = self._get_hash(key)
    key_value = [key, value]
    
    if self.map[key_hash] is None:
        self.map[key_hash] = [key_value]
        return True
    
    else:
        #check if it's an update
        for pair in self.map[key_hash]:
            if pair in self.map[key_hash]:
                if pair[0] == key:
                    print("updating: ", key)
                    pair[1] = value
                    return True
        # nope, it's a collision: insert it
        self.map[key_hash].append(key_value)
        return True
    
HashMap.add = add
h = HashMap()

h.add(17, "seventeen")
h.add(26, "Twenty six")
h.add(35, "Thirty five")
h.add(26, "Twenty six updated")
h.add(887, "large number")

print(h)
def delete(self, key):
    key_hash = self._get_hash(key)
    
    if self.map[key_hash] is None:
        raise KeyError(str(key))
        
    for i in range(0, len(self.map[key_hash])):
        if self.map[key_hash][i][0] == key:
            self.map[key_hash].pop(i)
            return True

HashMap.delete = delete
h.delete(17)
print(h)<jupyter_output>5: [[35, 'Thirty five']]
6: [[26, 'Twenty six updated']]
7: [[887, 'large number']]
{'fraction_non_alphanumeric': 0.14581734458940906, 'fraction_numerical': 0.019953952417498082, 'mean_word_length': 2.542119565217391, 'pattern_counts': {'":': 1, '<': 7, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '240231', 'license': 'MIT', 'n_tokens_mistral': 1000, 'n_tokens_neox': 961, 'n_words': 247, 'path': '16-hashmap.ipynb', 'repo_name': 'zexhan17/Data-Structures-and-Algorithms-using-Python', 'size': '2606'}