正文

Java散列和散列码的实现

IP云
IP云V管理员/4 阅读
10/30
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

转自：https://blog.csdn.net/al_assad/article/details/52989525

散列和散列码
 
※正确的equals方法应该满足的的条件：
①自反性：x.equals(x) 一定返回true；
②对称性：y.euqlas(x)为true，那么x.equals(y)一定为true；
③传递性：x.equals(y)为true，y.euqlas(z)为true，则z.equals(x)为true；
④一致性：如果x，y中用于等价比较的信息没有变化，那么无论调用y.euqlas(x)多少次，结果都是一致的；
⑤对任何不是null的x，x.equals(null)一定为false；
 
1、在查询方式里，线性查询是最慢的查询方式；
2、散列的价值在于速度，它使用一组数组（Java中储存查询速度最快的数据结构）来储存键的信息（并非键本身）；
     数组本身不保存键本身，而是通过键本身生成一个编码，将其作为数组下标，该编码就是散列码，由键的hashCode（散列函数）产生；
     数组保存的一个记录键的list，当在一个数组中的散列码发生冲突时，有外部链接解决冲突，并加入同一个list中；
3、在散列结构里查找一个键：
     ①计算该键的散列码，使用该散列码查询数组；
     ②对该数组下标的list使用根据equals进行线性查询；
4、散列表中的一些术语：
     ①容量：表中的桶buckets位数；
     ②初始容量：表在创建时拥有的桶位数，HashMap和HashSet都允许指定初始容量的构造器；
     ③尺寸：表中当前储存的位数；
     ④负载因子：尺寸/容量，空表负载为0，满表负载为1.0，负载轻产生的冲突可能性小，有利于插入和查询，但是会减慢使用迭代器遍历元素，默认的负载因子为0.75；
     ⑤再散列：当负载达到负载因子的水平时，容器会自动增加容量（双倍增加）；
5、散列容器的模型：
 
6、hashCode的实现：
 
 
7、HashMap的实现和key元素实现散列码
  1. <span style="color:#000000;">import java.util.*;
  2. public class SimpleHashMap<K,V> extends AbstractMap<K,V>{
  3. static final int SIZE = 997;  //默认bucket数量；
  4. @SuppressWarnings("unchecked")
  5. LinkedList<MapEntry<K,V>>[] buckets = new LinkedList[SIZE];
  6. //放置映射关系，返回原先的映射Value；
  7. public V put (K key, V value){
  8. int index = Math.abs(key.hashCode()) % SIZE;
  9. if(buckets[index] == null)
  10. buckets[index] = new LinkedList<MapEntry<K, V>>();
  11. V oldValue = null;
  12. LinkedList<MapEntry<K,V>> bucket = buckets[index];
  13. MapEntry<K, V> pair = new MapEntry<K,V>(key,value);
  14. ListIterator<MapEntry<K,V>> iter = bucket.listIterator();
  15. //检查重复key，更新value
  16. boolean found = false;
  17. while(iter.hasNext()){
  18. MapEntry<K,V> tempPair = iter.next();
  19. if(tempPair.getKey().equals(key)){
  20. oldValue = tempPair.getValue();
  21. iter.set(pair);
  22. found = true;
  23. break;
  24. }
  25. }
  26. if(!found)
  27. buckets[index].add(pair);
  28. return oldValue;
  29. }
  30. public V get(Object key){
  31. int index = Math.abs(key.hashCode()) % SIZE;
  32. if(buckets[index] == null)
  33. return null;
  34. for(MapEntry<K,V> pair : buckets[index]){
  35. if(pair.getKey().equals(key))
  36. return pair.getValue();
  37. }
  38. return null;
  39. }
  40. @Override
  41. public Set<Map.Entry<K, V>> entrySet() {
  42. Set<Map.Entry<K, V>> set = new HashSet<Map.Entry<K,V>>();
  43. for(LinkedList<MapEntry<K,V>> bucket : buckets){
  44. if(bucket == null)
  45. continue;
  46. for(MapEntry<K,V> pair : bucket)
  47. set.add(pair);
  48. }
  49. return set;
  50. }
  51. class MapEntry<K,V> implements Map.Entry<K, V>{
  52. K key;
  53. V value;
  54. public MapEntry(K key,V value){
  55. this.key = key;
  56. this.value = value;
  57. }
  58. @Override
  59. public K getKey(){
  60. return  this.key;
  61. }
  62. @Override
  63. public V getValue() {
  64. return this.value;
  65. }
  66. @Override
  67. public V setValue(V value) {
  68. return this.value = value;
  69. }
  70. }
  71. /*实现可以引用在在HashMap对象的key对象，该对象必须实现hashCode方法*/
  72. import java.util.*;
  73. public class CountString {
  74. private static List<String> created = new ArrayList<String>();
  75. //用于记录一次程序运行创建的所哟 String s实例，当s发生重复时，生成唯一的id，以产生唯一的散列值；
  76. private String s ;        //用于记录内容的数据域
  77. private int id = 0;             //记录相同String的CountString对象的编号
  78. public CountString(String str){
  79. this.s = str;
  80. created.add(s);
  81. for(String e : created){
  82. if(e.equals(s))
  83. this.id++;
  84. }
  85. }
  86. public int hashCode(){
  87. int result = 17;                //设置初始偏移量
  88. result = 37*result + s.hashCode();            //37稀释值
  89. result = 37*result + id;               //进行第二次稀释，放置ID值破坏s.hasCode；
  90. return result;
  91. }
  92. public boolean equals(Object o){
  93. return o instanceof CountString && s.equals(((CountString)o).getS())
  94. && id == ((CountString)o).getId();
  95. }
  96. public String getS(){
  97. return this.s;
  98. }
  99. public int getId(){
  100. return  this.getId();
  101. }
  102. public String toString(){
  103. return "String:"+s+" id:"+id+" hashCode: "+hashCode();
  104. }
  105. }
  106. </span>