java数据结构（哈希表）

2014-11-14 13:55:32 java基础 共1358人围观 0个不明物体
1.什么是哈希表？ 哈希表是一种数据结构，它提供了快速的插入操作和查找操作。其基于数组来实现。 2.哈希化 1)直接将关键字作为索引。 2)将单词转换成索引。 <1>将字母转换成ASCII码，然后进行相加 <2>幂的连乘 <3>压缩可选值 3.压缩后仍然可能出现的问题。 冲突：不能保证每个单词都映射到数组的空白单元。 解决办法： <1>开放地址法 <2>链地址法
Java代码  收藏代码
  1. /** 
  2.  * 员工信息类 
  3.  * @author Administrator 
  4.  * 
  5.  */
  6. public class Info {
  7.     private String key;
  8.     private String name;
  10.     public Info(String key, String name) {
  11.         this.key = key;
  12.         this.name = name;
  13.     }
  15.     public String getKey() {
  16.         return key;
  17.     }
  19.     public void setKey(String key) {
  20.         this.key = key;
  21.     }
  23.     public String getName() {
  24.         return name;
  25.     }
  27.     public void setName(String name) {
  28.         this.name = name;
  29.     }
  30. }
   
Java代码  收藏代码
  1. import java.math.BigInteger;
  3. public class HashTable {
  4.     private Info[] arr;
  6.     /** 
  7.      * 默认的构造方法 
  8.      */
  9.     public HashTable() {
  10.         arr = new Info[100];
  11.     }
  13.     /** 
  14.      * 指定数组初始化大小 
  15.      */
  16.     public HashTable(int maxSize) {
  17.         arr = new Info[maxSize];
  18.     }
  20.     /** 
  21.      * 插入数据 
  22.      */
  23.     public void insert(Info info) {
  24.         arr[hashCode(info.getKey())] = info;
  25.     }
  27.     /** 
  28.      * 查找数据 
  29.      */
  30.     public Info find(String key) {
  31.         return arr[hashCode(key)];
  32.     }
  34.     public int hashCode(String key) {
  35. //      int hashVal = 0; 
  36. //      for(int i = key.length() - 1; i >= 0; i--) { 
  37. //          int letter = key.charAt(i) - 96; 
  38. //          hashVal += letter; 
  39. //      } 
  40. //      return hashVal; 
  42.         BigInteger hashVal = new BigInteger("0");
  43.         BigInteger pow27 = new BigInteger("1");
  44.         for(int i = key.length() - 1; i >= 0; i--) {
  45.             int letter = key.charAt(i) - 96;
  46.             BigInteger letterB = new BigInteger(String.valueOf(letter));
  47.             hashVal = hashVal.add(letterB.multiply(pow27));
  48.             pow27 = pow27.multiply(new BigInteger(String.valueOf(27)));
  49.         }
  50.         return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue();
  51.     }
  52. }
   
Java代码  收藏代码
  1. public class TestHashTable {
  2.     public static void main(String[] args) {
  3.         HashTable ht = new HashTable();
  4.         ht.insert(new Info("a","张三"));
  5.         ht.insert(new Info("ct","李四"));
  6.         ht.insert(new Info("wangwu","王五"));
  8.         System.out.println(ht.find("a").getName());
  9.         System.out.println(ht.find("ct").getName());
  10.     }
  11. }
 

爆款云服务器s6 2核4G 低至0.46/天，具体规则查看活动详情Blog Img
标签：哈希表
网站公告
POWERED BY https://www.bugkong.com AND ALL RIGHTS RESERVED
java爱好者 网站地图 支持博主 蜀ICP备13022962号-3