>[success] # 链表法 ~~~ 1.上个章节'散列函数'是通过ascii 码的形式，这种形式会出现，虽然字符串不同，但是组成的 ascii码是一样的，这就出现了'散列冲突',解决其中一个方法就是使用链表的方法 2.如图就是当有相同的ascii码时候,存储的不在是单单对象值，而是一个链表依次连接 ~~~ * 如图  >[danger] ##### 代码实现 ~~~ class ValuePair { constructor(key, value) { this.key = key; this.value = value; } toString() { return `[#${this.key}: ${this.value}]`; } } function defaultToString(item) { if (item === null) { return 'NULL'; } if (item === undefined) { return 'UNDEFINED'; } if (typeof item === 'string' || item instanceof String) { return `${item}`; } return item.toString(); } class HashTableSeparateChaining { 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) { 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; } isEmpty() { return this.size() === 0; } size() { let count = 0; Object.values(this.table).forEach(linkedList => { count += linkedList.size(); }); return count; } clear() { this.table = {}; } getTable() { return this.table; } 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; } } ~~~