哈希表是一种高效的数据结构,它通过哈希函数将键映射到数组中的索引,实现快速的数据存储和检索。在实战中,它可用于高效地计算单词出现的次数:①使用哈希表将每个单词映射到一个计数器;②当遇到一个单词时,检查哈希表中是否有该键;③如果没有,就添加它并将计数设置为 1;④如果有,就将计数加 1。
PHP数据结构:哈希表的奥秘
哈希表简介
哈希表是一种高效的数据结构,用于存储和快速检索数据。它将键映射到值,并使用哈希函数将键转换为可以在数组中使用的索引。
哈希函数
哈希函数是将键转换为索引的神奇公式。理想的哈希函数是:
- 统一:为不同键生成不同的索引
- 快速:在恒定时间内计算
- 无冲突:避免为多个键生成相同的索引
实战案例:单词计数器
假设我们有一个文本文件,我们需要计算每个单词出现的次数。一个朴素的解决方案是使用一个数组来存储单词及其计数,但随着单词数量的增加,查找和更新计数的效率会降低。
使用哈希表,我们可以将每个单词映射到一个计数器,并直接使用单词作为键。当我们遇到一个单词时,我们可以快速检查哈希表中是否有这个键,如果没有,我们就添加它并将其计数设置为 1。如果有,我们就将计数加 1。
class WordCounter { private $words = []; public function countWords($text) { $words = explode(' ', $text); foreach ($words as $word) { if (isset($this->words[$word])) { $this->words[$word]++; } else { $this->words[$word] = 1; } } } public function getWordCount($word) { return $this->words[$word] ?? 0; } }
在这个例子中,$words数组充当哈希表,键是单词,值是计数。函数countWords()高效地计算每个单词的计数,而函数getWordCount()允许我们快速检索特定单词的计数。