扫一扫
分享文章到微信
扫一扫
关注官方公众号
至顶头条
Schema的优化和索引 - 索引的基础 - 索引的类型 - Hash索引5
如果你使用这种方法,不要使用SHA1()和MD5这些hash函数。这些返回了非常长的字符串。这会浪费空间和降低比较的速度。这两个函数密码性很强,也会消除冲突,但在这里这并不是我们的目标。简单的hash函数所造成的冲突是可容忍的并且还有良好的性能。
如果你的表中有很多行,CRC32函数可以造成太多的冲突。你可以自己实现64bit的hash函数。要确定的是,你使用的函数必须返回的是整型,并不是个字符串。实现64bit hash函数的方法是使用MD5所返回的一部分。这可能会比自定义函数的性能要差一些,但是必要时可以这么做。
mysql> SELECT CONV(RIGHT(MD5('http://www.mysql.com/'), 16), 16, 10) AS HASH64;
+---------------------+
| HASH64 |
+---------------------+
| 9761173720318281581 |
+---------------------+
Maatkit(http://maatkit.sourceforge.net)包含了一个自定义函数,实现了一个Fowler/Noll/Vo 64bit hash函数。它的速度也非常快。
处理hash冲突
如果你要使用hash来搜索的话,你必须要在WHERE条件中包含它hash之前的值。比如
mysql> SELECT id FROM url WHERE url_crc=CRC32("http://www.mysql.com")
-> AND url="http://www.mysql.com";
下面的语句就不是正确的。因为另一个URL的Hash值也是1560514994,这个语句会把它们都查找出来。
mysql> SELECT id FROM url WHERE url_crc=CRC32("http://www.mysql.com");
Hash的冲突情况增长的速度可能超出你的想象。这是由于所谓的Birthday Paradox所引起的。CRC32()返回的一个32bit整型值。因此可能93000值就会有1%的冲突。为了证明这点,我们把/usr/share/dict/words所有word写入到表中。结果写入了98,569行。已经有了一个冲突了。冲突会使以下的查询返回很多行
mysql> SELECT word, crc FROM words WHERE crc = CRC32('gnu');
+---------+------------+
| word | crc |
+---------+------------+
| codding | 1774765869 |
| gnu | 1774765869 |
+---------+------------+
正确的查询语句
mysql> SELECT word, crc FROM words WHERE crc = CRC32('gnu') AND word = 'gnu';
+------+------------+
| word | crc |
+------+------------+
| gnu | 1774765869 |
+------+------------+
为了避免冲突,你必须在where条件中同时指定这两个条件。如果冲突不是一个问题,就在WHERE条件后仅仅指定CRC32,这个情况下,你可能执行的是关于统计的语句而不需要准确的结果。这样还能获得更高的效率。
如果您非常迫切的想了解IT领域最新产品与技术信息,那么订阅至顶网技术邮件将是您的最佳途径之一。
现场直击|2021世界人工智能大会
直击5G创新地带,就在2021MWC上海
5G已至 转型当时——服务提供商如何把握转型的绝佳时机
寻找自己的Flag
华为开发者大会2020(Cloud)- 科技行者