什么是哈希表
首先说说什么是表?顾名思义,就是通过提供的key随机访问到value。那么哈希表,就是通过哈希的方式来实现表。什么叫哈希?哈希又叫散列,就是把任意长度的输入通过哈希函数转化成固定长度的输出,而这个输出就是哈希值。
哈希表种类和实现
哈希表一般分为两种:链式哈希表,开地址哈希表。
链表哈希表,一般是每个任意长度的输入通过哈希函数转化成固定长度的输出,然后放到桶(Bucket)里。如果出现不同的输入产生同样的哈希值就碰撞了,碰撞了就追加到桶里,碰撞的越多,桶就越满。
开地址哈希表,一般是每个任意长度的输入通过哈希函数转化成固定长度的输出,放到哈希值对应的slot里,如果冲突了就继续哈希(另外一种哈希方法),直到找到一个空的slot为止。
哈希表的用途
一般随机访问的都可以使用哈希表来实现。最为我们熟知的用法,可能就是编译是产生的symbol table了。
阅读(3665) | 评论(0) | 转发(1) |