# hash table 2
class ListNode(object):
    def __init__(self, key, val, next=None):
        self.key = key
        self.val = val
        self.next = next


class hashTable2(object):
    def __init__(self):
        self.capacity = 4
        self.size = 0
        self.table = [None for _ in range(self.capacity)]


    def put(self, key, value):
        # new key insert, increase size
        if self.get(key) is None:
            self.size += 1

        self.addListNode(self.table, key, value, self.capacity)

        if self.size >= self.capacity * 0.7:
            self.rehashing(self.capacity * 2)

    # find value, O(1 + k), k is the average length of the node list
    def get(self, key):
        # get the index with the hash of key
        index = self.indexFor(key, self.capacity)

        # no nodeList, return None
        if self.table[index] == None:
            return None

        # traverse through the listNode to find the key, value
        node = self.table[index]
        while node:
            if node.key == key:
                return node.val
            node = node.next

        return None

    def rehashing(self, newCapacity):
        self.capacity = newCapacity  # update capacity
        self.size = 0
        newTable = [None] * newCapacity
        # transfer old table to newTable
        for node in self.table:
            while node:
                self.addListNode(newTable, node.key, node.val, newCapacity)
                self.size += 1
                node = node.next

        self.table = newTable  # update old table reference to newTable

    def addListNode(self, table, key, value, length):
        index = self.indexFor(key, length)

        if table[index] == None:
            table[index] = ListNode(key, value)
            return

        # traverse through nodelist to find the key match
        prev = table[index]
        cur = table[index]
        while cur:
            if cur.key == key:
                cur.val = value
                return
            prev = cur
            cur = cur.next

        # no key match, add new ListNode(key, val) add the tail
        prev.next = ListNode(key, value)

    def indexFor(self, key, length):
        return hash(key) % length

table = hashTable2()
table.put("a", 1)
table.put("b", 2)
table.put("c", 3)
table.put('d', 10)
table.put('e', 11)
table.put('f', 12)
table.put('a', 10)

print(table.get("a"))
print(table.get("b"))
print(table.get("c"))
print(table.get("d"))
print(table.get("e"))
print(table.get("f"))

print("capacity", table.capacity)