1.什么是哈希表？
哈希表是一种数据结构，它提供了快速的插入操作和查找。其基于数组来实现。
2.哈希化
1).直接将关键字作为索引。
2).将单词转换成索引。
- 将字母转换成ASCII码，然后进行相加（容易出现重复的哈希值，如：abc，bbb和cba的值是相同的）
- 幂的连乘（哈希值的长度可能超过int和long类型的长度）
- 压缩可选值（推荐使用）
3.压缩后仍然可能出现的问题
冲突，不能保证每个单词都映射到数组的空白单元。
解决办法：
- 开放地址法：当冲突发生时，通过查找数组的一个空位，并将数据填入，而不再用哈希函数得到的数组下标，这个方法叫做开放地址法。
- 链地址法：在哈希表每个单元中设置链表。某个数据项的关键字还是像通常一样映射到哈希表的单元中，而数据项本身插入到单元的链表中。
4.代码示例（开放地址法）：
1 /** 2 * 员工信息类 3 */ 4 public class Info { 5 private String key;//哈希值 6 private String name;//员工姓名 7 8 public Info(String key, String name){ 9 this.key = key;10 this.name = name;11 }12 13 public String getKey(){14 return key;15 }16 public void setKey(String key){17 this.key = key;18 }19 20 public String getName(){21 return name;22 }23 public void setName(String name){24 this.name = name;25 }26 27 }
1 public class HashTable { 2 private Info[] arr; 3 4 /** 5 * 默认的构造方法 6 */ 7 public HashTable(){ 8 arr = new Info[100]; 9 }10 11 /**12 * 指定数组初始化大小13 */14 public HashTable(int maxSize){15 arr = new Info[maxSize];16 }17 18 /**19 * 插入数据20 */21 public void insert(Info info){22 23 //获得关键字24 String key = info.getKey();25 //关键字所指定的哈希数26 int hashVal = hashCode(key);27 //如果这个索引已经被占用，而且里面是一个未被删除的数据28 while(arr[hashVal] != null && arr[hashVal].getName() != null){29 //进行递加30 ++ hashVal;31 //循环32 hashVal %= arr.length;33 }34 arr[hashVal] = info;35 36 }37 38 /**39 * 查找数据40 */41 public Info find(int key){42 int hashVal = hashCode(key);43 while(arr[hashVal] != null){44 if(arr[hashVal].getKey().equal(key)){45 return arr[hashVal];46 }47 ++ hashVal;48 hashVal %= arr.length;49 }50 return null;51 }52 53 /**54 * 删除数据55 */56 public Info delete(String key){57 int hashVal = hashCode(key);58 while(arr[hashVal] != null){59 if(arr[hashVal].getKey().equal(key)){60 Info tmp = arr[hashVal];61 tmp.setName(null);62 return tmp;63 }64 ++ hashVal;65 hashVal %= arr.length;66 }67 return null;68 }69 70 public int hashCode(String key){71 // int hashVal = 0;72 // for(int i = key.length() - 1; i >= 0; i++){73 // int letter = key.charAt(i) - 96;74 // hashVal += letter;75 // }76 // return hashVal;77 78 BigInteger hashVal = new BigInteger("0");79 BigInteger pow27 = new BigInteger("1")80 for(int i = key.length() - 1; i >= 0; i++){81 int letter = key.charAt(i) - 96;82 BigInteger letterB = new BigInteger(String.valueOf(letter));83 hashVal = hashVal.add(letterB.multiply(pow27));84 pow27 = pow27.multiply(new BigInteger(String.valueOf(27)));85 }86 return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue();87 88 }89 }
1 /** 2 * 测试类 3 */ 4 public class TestHashTable { 5 public static void main(String[] args) { 6 HashTable ht = new HashTable(); 7 ht.insert(new Info("zhangsan","张三")); 8 ht.insert(new Info("lisi","李四")); 9 ht.insert(new Info("wangwu","王五"));10 11 System.out.println(ht.find("zhangsan").getName());12 System.out.println(ht.find("lisi").getName());13 System.out.println(ht.find("lisi").getName());14 }15 }