字典和哈希表

一、字典

字典（Dictionary） 是一种数据结构，它将唯一的键映射到相应的值上。每个键都是唯一的，而且与一个特定的值相关联。字典提供了一种通过键来快速查找值的方式。字典不要求键的顺序，因此不能通过索引来访问。在一些编程语言中，字典可能被实现为基于哈希表的数据结构。

// JavaScript 中的字典示例
let dictionary = {
  key1: 'value1',
  key2: 'value2',
  key3: 'value3'
}

console.log(dictionary['key1']) // 输出: value1

二、哈希表

哈希表（Hash Table） 是一种通过散列函数将键映射到数组索引的数据结构。散列函数负责将键映射为数组中的一个位置。理想情况下，散列函数应该使得键均匀地分布在数组中，以减少冲突。

// JavaScript 中的哈希表示例
class HashTable {
  constructor() {
    this.table = new Array(100) // 假设数组大小为100
  }

  // 简单的散列函数
  hash(key) {
    let hash = 0
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i)
    }
    return hash % this.table.length
  }

  // 插入键值对
  insert(key, value) {
    const index = this.hash(key)
    this.table[index] = value
  }

  // 获取键对应的值
  get(key) {
    const index = this.hash(key)
    return this.table[index]
  }
}

// 创建哈希表实例
const hashTable = new HashTable()
hashTable.insert('name', 'John')
console.log(hashTable.get('name')) // 输出: John

三、区别和总结

• 区别：

  • 字典强调键值对的概念，而哈希表是一种基于散列函数实现的键值对存储和检索的数据结构。
  • 字典可能使用不同的底层实现，而哈希表通常具有特定的散列函数和解决冲突的机制。

• 共同点：

  • 字典和哈希表都用于存储键值对，提供快速的检索能力。