CLRS笔记11,Hash Table 博客分类： Infrastructure MySQL数据结构.netHTMLBlog

Hash Table是实现动态集合在O(1)时间内的INSERT、SEARCH和DELETE的一种数据结构
基本原理是选择一种哈希函数，将key进行哈希函数求值后的数值结果作为索引，然后实现直接寻址

哈希求值后的结果可能重复，称为冲突，可以用链接法和开放寻址法解决

参考:
http://baike.baidu.com/view/1207363.html
http://en.wikipedia.org/wiki/Hash_table


Hash Table由于出色的性能而应用在很多地方，如MySQL的索引:

CREATE [UNIQUE|FULLTEXT|SPATIAL] INDEX index_name
    [index_type]
    ON tbl_name (index_col_name,...)
    [index_type]

index_col_name:
    col_name [(length)] [ASC | DESC]

index_type:
    USING {BTREE | HASH | RTREE}

Storage Engine Allowable Index Types

MyISAM 	BTREE, RTREE
InnoDB 	BTREE
MEMORY/HEAP 	HASH, BTREE
NDB 	HASH, BTREE (see note in text)

BTREE和RTREE下次再看
参考:
http://dev.mysql.com/doc/refman/5.0/en/create-index.html
http://blog.csdn.net/whyangwanfu/archive/2008/09/21/2958762.aspx