免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
› 论坛 › 程序设计 › Java › Hash表
最近访问板块 发新帖
查看: 1920 | 回复: 0
打印 上一主题 下一主题

Hash表 [复制链接]

feiyang10086

论坛徽章:
0
跳转到指定楼层
1楼 [收藏(0)] [报告]
发表于 2011-11-27 10:28 |只看该作者 |倒序浏览
  Hash表








这个代码是自己模拟哈希表实现的一个简单的学生统计系统，具体是实现的散列表中的开散列，即用数组保存一组数据，这一组数据中通过链表连结彼此，于是达到增加，查找，替换，删除的功能。
  hash的预映射算法比较简单，即将学生学号的各个位相加，得到的个位数数值即为散列值，因为个位数所以数组大小为10.

Java代码
  1. 1.private int handdata(Student stu) {   
  2. 2.        int num = stu.numb;   
  3. 3.        while (num > 9) {//循环运算直到num变为个位数   
  4. 4.            num = num / 10000 + num % 10000 / 1000 + num % 1000 / 100 + num   
  5. 5.                    % 100 / 10 + num % 10;//将各个位的值相加的运算   
  6. 6.        }   
  7. 7.        return num;   
  8. 8.    }  
  9. private int handdata(Student stu) {
  10.                 int num = stu.numb;
  11.                 while (num > 9) {//循环运算直到num变为个位数
  12.                         num = num / 10000 + num % 10000 / 1000 + num % 1000 / 100 + num
  13.                                         % 100 / 10 + num % 10;//将各个位的值相加的运算
  14.                 }
  15.                 return num;
  16.         }
复制代码
接下来要设计学生的类，这也是hash表中数组中保存的对象的类。

Java代码
  1. 1.public class Student {   
  2. 2.    public String name="11";   
  3. 3.    public int numb=11111;   
  4. 4.    public int gride=11;   
  5. 5.    public Student before=null;   
  6. 6.    public Student next=null;   
  7. 7.      
  8. 8.    /**  
  9. 9.     * 重新构造方法以传入数值  
  10. 10.     * @param name  
  11. 11.     * @param numb  
  12. 12.     * @param gride  
  13. 13.     */  
  14. 14.    public Student(String name,int numb,int gride){   
  15. 15.        this.name=name;   
  16. 16.        this.gride=gride;   
  17. 17.        this.numb=numb;   
  18. 18.    }   
  19. 19.      
  20. 20.    //这个构造方法用来实现默认的对象   
  21. 21.    public Student(){         
  22. 22.    }   
  23. 23.      
  24. 24.    //改变对象下一个和上一下结点的方法   
  25. 25.    public void changenext(Student s){   
  26. 26.        next=s;   
  27. 27.    }   
  28. 28.      
  29. 29.    public void changebefore(Student s){   
  30. 30.        before=s;   
  31. 31.    }   
  32. 32.}  
  33. public class Student {
  34.         public String name="11";
  35.         public int numb=11111;
  36.         public int gride=11;
  37.         public Student before=null;
  38.         public Student next=null;
  39.        
  40.         /**
  41.          * 重新构造方法以传入数值
  42.          * @param name
  43.          * @param numb
  44.          * @param gride
  45.          */
  46.         public Student(String name,int numb,int gride){
  47.                 this.name=name;
  48.                 this.gride=gride;
  49.                 this.numb=numb;
  50.         }
  51.        
  52.         //这个构造方法用来实现默认的对象
  53.         public Student(){               
  54.         }
  55.        
  56.         //改变对象下一个和上一下结点的方法
  57.         public void changenext(Student s){
  58.                 next=s;
  59.         }
  60.        
  61.         public void changebefore(Student s){
  62.                 before=s;
  63.         }
  64. }
复制代码
创建hash表和向其中加入元素的方法
  这里要注意的是在加入新对象时记得去掉默认的对象

Java代码
  1. 1./**  
  2. 2. * 创建hash表的方法  
  3. 3. * @param stu  
  4. 4. */  
  5. 5.public void createHash(Student stu) {   
  6. 6.    for (int i = 0; i < 10; i++) {   
  7. 7.        Student st = new Student();   
  8. 8.        hash[i] = st;   
  9. 9.    }//首先默认对数组每个下标值对应的加入一个对象   
  10. 10.    int hashcode = handdata(stu);//获得散列值   
  11. 11.    hash[hashcode] = stu;//加入对象   
  12. 12.}   
  13. 13.  
  14. 14./**  
  15. 15. * 向hash表内加入元素的方法  
  16. 16. * @param stu  
  17. 17. */  
  18. 18.public void addHash(Student stu) {   
  19. 19.    int hashcode = handdata(stu);   
  20. 20.    if (hash[hashcode] == null) {   
  21. 21.        hash[hashcode] = stu;   
  22. 22.    } else {//如果此散列值对应的不为空，那么去掉默认的对象（如果有），加入新对象   
  23. 23.        Student stut = hash[hashcode];   
  24. 24.        if (stut.name.equals("11")) {   
  25. 25.            hash[hashcode] = stu;   
  26. 26.        } else {   
  27. 27.            while (stut.next != null) {   
  28. 28.                stut = stut.next;   
  29. 29.            }   
  30. 30.            stut.next = stu;   
  31. 31.        }   
  32. 32.    }   
  33. 33.}  
  34.         /**
  35.          * 创建hash表的方法
  36.          * @param stu
  37.          */
  38.         public void createHash(Student stu) {
  39.                 for (int i = 0; i < 10; i++) {
  40.                         Student st = new Student();
  41.                         hash[i] = st;
  42.                 }//首先默认对数组每个下标值对应的加入一个对象
  43.                 int hashcode = handdata(stu);//获得散列值
  44.                 hash[hashcode] = stu;//加入对象
  45.         }

  47.         /**
  48.          * 向hash表内加入元素的方法
  49.          * @param stu
  50.          */
  51.         public void addHash(Student stu) {
  52.                 int hashcode = handdata(stu);
  53.                 if (hash[hashcode] == null) {
  54.                         hash[hashcode] = stu;
  55.                 } else {//如果此散列值对应的不为空，那么去掉默认的对象（如果有），加入新对象
  56.                         Student stut = hash[hashcode];
  57.                         if (stut.name.equals("11")) {
  58.                                 hash[hashcode] = stu;
  59.                         } else {
  60.                                 while (stut.next != null) {
  61.                                         stut = stut.next;
  62.                                 }
  63.                                 stut.next = stu;
  64.                         }
  65.                 }
  66.         }
复制代码
查找表中已存在的元素很简单，即将它的学号处理得到散列值然后遍历hash表即可（这里给予的值可以是学生类的对象，也可以是学生的学号，大体上没什么区别）

Java代码
  1. 1.public Student seekHash(Student stu) {   
  2. 2.        int hashcode = handdata(stu);   
  3. 3.        Student stu2 = hash[hashcode];   
  4. 4.        while (stu2.numb != stu.numb) {//反复查找直到找到对应的对象   
  5. 5.            stu2 = stu2.next;   
  6. 6.        }   
  7. 7.        System.out.println("姓名：" + stu2.name + "\t学号：" + stu2.numb + "\t分数："  
  8. 8.                + stu2.gride);   
  9. 9.        System.out.println("查找完成。");   
  10. 10.        return stu2;   
  11. 11.    }  
  12. public Student seekHash(Student stu) {
  13.                 int hashcode = handdata(stu);
  14.                 Student stu2 = hash[hashcode];
  15.                 while (stu2.numb != stu.numb) {//反复查找直到找到对应的对象
  16.                         stu2 = stu2.next;
  17.                 }
  18.                 System.out.println("姓名：" + stu2.name + "\t学号：" + stu2.numb + "\t分数："
  19.                                 + stu2.gride);
  20.                 System.out.println("查找完成。");
  21.                 return stu2;
  22.         }
复制代码
替换表中元素和删除表中元素其实差不多，都是找到这个对象然后改变它父结点和子结点中指针的指向来达到目的的，其中要注意的就是找到的这个结点可能没有父结点或子结点，这时需要分开讨论（由于删除牵涉到2个需要讨论的结点之间的操作，所以比替换略复杂）

Java代码
  1. 1./**  
  2. 2.     * 替换hash表元素的方法  
  3. 3.     *   
  4. 4.     * @param stu1  
  5. 5.     * @param stu2  
  6. 6.     */  
  7. 7.    public void changeHash(Student stu1, Student stu2) {   
  8. 8.        int hashcode = handdata(stu1);   
  9. 9.        Student stu = seekHash(stu1);   
  10. 10.        if (stu.before != null) {//分before和next讨论   
  11. 11.            Student stu3 = stu.before;   
  12. 12.            stu3.next = stu2;   
  13. 13.            stu2.before = stu3;   
  14. 14.        } else {   
  15. 15.            hash[hashcode] = stu2;   
  16. 16.        }   
  17. 17.        if (stu.next != null) {   
  18. 18.            Student stu4 = stu.next;   
  19. 19.            stu4.before = stu2;   
  20. 20.            stu2.next = stu4;   
  21. 21.        }   
  22. 22.    }   
  23. 23.  
  24. 24.    /**  
  25. 25.     * 删除hash表元素的方法  
  26. 26.     *   
  27. 27.     * @param stu  
  28. 28.     */  
  29. 29.    public void deleteHash(Student stu) {   
  30. 30.        int hashcode = handdata(stu);   
  31. 31.        Student stu0 = seekHash(stu);   
  32. 32.        if (stu0.before != null && stu0.next != null) {//各种讨论   
  33. 33.            Student stu1 = stu0.before;   
  34. 34.            Student stu2 = stu0.next;   
  35. 35.            stu1.next = stu2;   
  36. 36.            stu2.before = stu1;   
  37. 37.        } else if(stu0.before == null && stu0.next == null){   
  38. 38.            hash[hashcode] = new Student();   
  39. 39.        }else if(stu0.before == null && stu0.next != null){   
  40. 40.            Student stu3=stu0.next;   
  41. 41.            stu3.before=null;   
  42. 42.        }else if(stu0.before != null && stu0.next == null){   
  43. 43.            Student stu4=stu0.before;   
  44. 44.            stu4.next=null;   
  45. 45.        }   
  46. 46.    }  
  47. /**
  48.          * 替换hash表元素的方法
  49.          *
  50.          * @param stu1
  51.          * @param stu2
  52.          */
  53.         public void changeHash(Student stu1, Student stu2) {
  54.                 int hashcode = handdata(stu1);
  55.                 Student stu = seekHash(stu1);
  56.                 if (stu.before != null) {//分before和next讨论
  57.                         Student stu3 = stu.before;
  58.                         stu3.next = stu2;
  59.                         stu2.before = stu3;
  60.                 } else {
  61.                         hash[hashcode] = stu2;
  62.                 }
  63.                 if (stu.next != null) {
  64.                         Student stu4 = stu.next;
  65.                         stu4.before = stu2;
  66.                         stu2.next = stu4;
  67.                 }
  68.         }

  70.         /**
  71.          * 删除hash表元素的方法
  72.          *
  73.          * @param stu
  74.          */
  75.         public void deleteHash(Student stu) {
  76.                 int hashcode = handdata(stu);
  77.                 Student stu0 = seekHash(stu);
  78.                 if (stu0.before != null && stu0.next != null) {//各种讨论
  79.                         Student stu1 = stu0.before;
  80.                         Student stu2 = stu0.next;
  81.                         stu1.next = stu2;
  82.                         stu2.before = stu1;
  83.                 } else if(stu0.before == null && stu0.next == null){
  84.                         hash[hashcode] = new Student();
  85.                 }else if(stu0.before == null && stu0.next != null){
  86.                         Student stu3=stu0.next;
  87.                         stu3.before=null;
  88.                 }else if(stu0.before != null && stu0.next == null){
  89.                         Student stu4=stu0.before;
  90.                         stu4.next=null;
  91.                 }
  92.         }
复制代码
以上就是我的简单的开散列，下面附上实例结果，分别为创建添加，替换，删除后的遍历结果（查找已在替换和删除中体现）

引用
数组第0个中的元素：
  1. 姓名：lihao1 学号：0 分数：87
  2. 数组第1个中的元素：
  3. 姓名：lihao2 学号：1 分数：86
  4. 姓名：lihao3 学号：1 分数：85
  5. 数组第2个中的元素：
  6. 姓名：lihao4 学号：2 分数：84
  7. 数组第3个中的元素：
  8. 姓名：11 学号：11111 分数：11
  9. 数组第4个中的元素：
  10. 姓名：11 学号：11111 分数：11
  11. 数组第5个中的元素：
  12. 姓名：11 学号：11111 分数：11
  13. 数组第6个中的元素：
  14. 姓名：11 学号：11111 分数：11
  15. 数组第7个中的元素：
  16. 姓名：11 学号：11111 分数：11
  17. 数组第8个中的元素：
  18. 姓名：11 学号：11111 分数：11
  19. 数组第9个中的元素：
  20. 姓名：11 学号：11111 分数：11
  21. 一次遍历完成。

  23. 姓名：lihao4 学号：2 分数：84
  24. 一次查找完成。

  26. 数组第0个中的元素：
  27. 姓名：lihao1 学号：0 分数：87
  28. 数组第1个中的元素：
  29. 姓名：lihao2 学号：1 分数：86
  30. 姓名：lihao3 学号：1 分数：85
  31. 数组第2个中的元素：
  32. 姓名：lihao5 学号：2 分数：88
  33. 数组第3个中的元素：
  34. 姓名：11 学号：11111 分数：11
  35. 数组第4个中的元素：
  36. 姓名：11 学号：11111 分数：11
  37. 数组第5个中的元素：
  38. 姓名：11 学号：11111 分数：11
  39. 数组第6个中的元素：
  40. 姓名：11 学号：11111 分数：11
  41. 数组第7个中的元素：
  42. 姓名：11 学号：11111 分数：11
  43. 数组第8个中的元素：
  44. 姓名：11 学号：11111 分数：11
  45. 数组第9个中的元素：
  46. 姓名：11 学号：11111 分数：11
  47. 一次遍历完成。

  49. 姓名：lihao5 学号：2 分数：88
  50. 一次查找完成。

  52. 数组第0个中的元素：
  53. 姓名：lihao1 学号：0 分数：87
  54. 数组第1个中的元素：
  55. 姓名：lihao2 学号：1 分数：86
  56. 姓名：lihao3 学号：1 分数：85
  57. 数组第2个中的元素：
  58. 姓名：11 学号：11111 分数：11
  59. 数组第3个中的元素：
  60. 姓名：11 学号：11111 分数：11
  61. 数组第4个中的元素：
  62. 姓名：11 学号：11111 分数：11
  63. 数组第5个中的元素：
  64. 姓名：11 学号：11111 分数：11
  65. 数组第6个中的元素：
  66. 姓名：11 学号：11111 分数：11
  67. 数组第7个中的元素：
  68. 姓名：11 学号：11111 分数：11
  69. 数组第8个中的元素：
  70. 姓名：11 学号：11111 分数：11
  71. 数组第9个中的元素：
  72. 姓名：11 学号：11111 分数：11
  73. 一次遍历完成。
复制代码
java
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号：11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们：huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP