function defaultToString(item) {
  if (item === null) {
    return 'NULL';
  } else if (item === undefined) {
    return 'UNDEFINED';
  } else if (typeof item === 'string' || item instanceof String) {
    return `${item}`;
  }
  return item.toString();
}

class ValuePair {
  constructor (key, value) {
    this.key = key
    this.value = value
  }
  toString () {
    return `[#${this.key}: ${this.value}]`
  }
}

class HashTable {
  constructor(toStrFn = defaultToString) {
    this.toStrFn = toStrFn
    this.table = {}
  }
  // 創建散列函數
  loseloseHashCode (key) {
    if (typeof key === 'number') return key
    const tableKey = this.toStrFn(key)
    let hash = 0
    for (let i = 0; i < tableKey.length; i++) {
      hash += tableKey.charCodeAt(i)
    }
    return hash % 37
  }
  hashCode (key) {
    return this.loseloseHashCode(key)
  }
  // 更新 或 新增
  put (key, value) {
    if (key != null && value != null) {
      this.table[this.toStrFn(key)] = new ValuePair(key, value)
      return true
    }
    return false
  }
  remove (key) {
    const hash = this.hashCode(key)
    const valuePair = this.table[hash]
    if (valuePair != null) {
      delete this.table[hash]
      return true
    }
    return false
  }
  get (key) {
    const valuePair = this.table[this.hashCode(key)]
    return valuePair == null ? undefined : valuePair.value
  }

  toString () {
    if (this.isEmpty()) return ''
    const keys = Object.keys(this.table)
    let objString = `{${keys[0]} => ${this.table[keys[0].toString()]}}`
    for (let i = 1; i < keys.length; i++) {
      objString = `${objString},{${keys[i]} => ${this.table[keys[i].toString()]}}`
    }
    return objString
  }
}

class HashTableSeparateChaining {
  constructor(toStrFn = defaultToString) {
    this.toStrFn = toStrFn
    this.table = {}
  }
  put (key, value) {
    if (key != null && value != null) {
      const position = this.hashCode(key)
      if (this.table[position] == null) {
        this.table[position] = new LinkedList()
      }
      this.table[position].push(new ValuePair(key. value))
      return true
    }
    return false
  }

  get (key) {
    const position = this.hashCode(key)
    const linkedList = this.table[position]
    if (linkedList != null && !linkedList.isEmpty()) {
      let current = linkedList.getHead()
      while (current != null) {
        if (current.element.key === key) {
          return current.element.value
        }
        current = current.next
      }
    }
    return undefined
  }

  remove (key) {
    const position = this.hashCode(key)
    const linkedList = this.table[position]
    if (linkedList != null && !linkedList.isEmpty()) {
      let current = linkedList.getHead()
      while (current != null) {
        if (current.element.key === key) {
          linkedList.remove(current.element)
          if (linkedList.isEmpty()) {
            delete this.table[position]
          }
          return true
        }
        current = current.next
      }
    }
    return false
  }
}

put (key, value) {
  if (key != null && value != null) {
    const position = this.hashCode(key)
    if (this.table[position] == null) {
      this.table[position] = new ValuePair(key, value)
    } else {
      let index = position + 1
      while (this.table[index] != null) {
        index++
      }
      this.table[index] = new ValuePair(key, value)
    }
    return true
  }
  return false
}

get (key) {
  const position = this.hashCode(key)
  if (this.table[position] != null) {
    if (this.table[position].key === key) {
      return this.table[position].value
    }
    let index = position + 1
    while (this.table[index] != null && this.table[index].key !== key) {
      index++
    }
    if (this.table[index] != null && this.table[index].key === key) {
      return this.table[index].value
    }
  }
  return undefined
}

remove (key) {
  const position = this.hashCode(key)
  if (this.table[position] != null) {
    if (this.table[position].key === key) {
      delete this.table[position]
      this.verifyRemoveSideEffect(key, position)
      return true
    }
    let index = position + 1
    while (this.table[index] != null && this.table[index].key !== key) {
      index++
    }
    if (this.table[index] != null && this.table[index].key === key) {
      delete this.table[index]
      this.verifyRemoveSideEffect(key, position)
      return true
    }
  }
  return false
}

verifyRemoveSideEffect (key, removePosition) {
  const hash = this.hashCode(key)
  let index = removePosition + 1
  while (this.table[index] != null) {
    const posHash = this.hashCode(this.table[index].key)
    if (posHash <= hash || posHash <= removePosition>) {
      this.table[removedPosition] = this.table[index]
      delete this.table[index]
      removePosition = index
    }
    index++
  }
}

djb2HashCode (key) {
  const tableKey = this.toStrFn(key)
  let hash = 5381
  for (let i=0; i < tableKey.length>; i++) {
    hash = (hash*33) + tableKey.charAt(i)
  }
  return hash % 1013
}