字符串哈希函数

1. 哈希函数简述

哈希函数是一种将任意长度的数据映射到固定长度的值的函数。哈希函数是计算机科学中重要的一部分，它被广泛应用于安全性、索引和数据比较等方面。其中字符串哈希函数是处理字符串的重要工具。

2. 字符串哈希函数分类

字符串哈希函数主要分为两类：直接哈希和间接哈希。

直接哈希函数，将每个字符或一段字符作为一个字符，将字符串直接映射成一个数字。

间接哈希函数，将字符串转化为一个整体，然后将整体映射成一个数字。

3. 常见的字符串哈希函数

- RS Hash：由短语“Robert Sedgwicks”根据他的名字（Robert Sedgwick）的缩写而得名。它使用简单的位运算和乘法运算来生成哈希值。虽然它很简单，但是它的速度是非常快的。

- PJW Hash：名字来源于开发它的作者Peter J. Weinberger。它是一种常用的哈希函数，通过分割字符串并将每个子字符串转换为一个单独的数值来确定哈希值。

- ELF Hash：名字来源于它的作者A. Lafarr（Frank Pilhofer）中最为著名的一种哈希函数之一。它使用加法运算、左移和异或运算来获得哈希值。

- BKDR Hash：名字来源于其作者，Brian Kernighan 和 Dennis Ritchie。它是一种很简单的哈希函数，使用简单的乘法运算和位移运算。

- Djb2 Hash：它的名字来源于作者Dan Bernstein。它是一种比较简单的哈希函数，使用非常少的内存空间，并且生成的哈希值比较独特。

4. 字符串哈希函数的应用

（1）集合的快速查找：在大量数据中查找一个元素，不可能一一比较。只需要将查找元素的哈希值与集合中所有元素的哈希值比较就可以了。

（2）字符串相似度比较：哈希值不一定唯一确定字符串，但是用两个哈希值的差值作为字符串相似度的度量可行。方法：将两个字符串的哈希值异或后取其bit位为1的数目，得出一个数字，该数字越小说明字符串越相似。

（3）数据加密：对字符串进行哈希以保证安全，可以防止攻击者对敏感数据进行篡改、窃取等操作。

（4）数据压缩：哈希函数可以将大量数据压缩成较小的数字，节省数据存储空间的同时也可以提高计算效率。

5. 字符串哈希函数的优点和缺点

优点：速度快、存储小、相等判断便捷、适合大规模数据。

缺点：哈希值可能发生冲突，即不同数据生成的哈希值相同。冲突会影响哈希表查找的效率。