有书共读07笔记【算法图解】第5章-散列表（java描述）

什么是散列表？

如果用专业术语来表达的话，我们会说，散列函数“将输入映射到数字”。你可能认为散列
函数输出的数字没什么规律，但其实散列函数必须满足一些要求。
它必须是一致的。例如，假设你输入apple时得到的是4，那么每次输入apple时，得到的都
必须为4。如果不是这样，散列表将毫无用处。
它应将不同的输入映射到不同的数字。 例如， 如果一个散列函数不管输入是什么都返回1，
它就不是好的散列函数。最理想的情况是，将不同的输入映射到不同的数字。

（本文一律采用java来说）

1.从HashMap说起

•    自反性 x.equals(x) 一定返回true
•    对称性 x.equals(y)返回true，则y.equals(x) 也返回true
•    传递性 x.equals(y)返回true,y.equals(z)返回true,则x.equals(y)返回true
•    一致性 如果对象中的信息没有改变，x.equals(y)要么一直返回true，要么一直返回false

2.散列

而这种办法所产生的问题就是下标重复。而我们的解决办法就是配合equals来确定键值。

3.HashCode

    public static int hashCode(int value) {
         return value;
     }

这里不在多说，我们自己的类有自己的散列码实现就好。

4. 以HashMap的get方法来说明

     public V get(Object key) {
         if (key == null) {
             HashMapEntry<K, V> e = entryForNullKey;
             return e == null ? null : e.value;
         }
         int hash = Collections.secondaryHash(key);
         HashMapEntry<K, V>[] tab = table;
         for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
                 e != null; e = e.next) {
             K eKey = e.key;
             if (eKey == key || (e.hash == hash && key.equals(eKey))) {
                 return e.value;
             }
         }
         return null;
     }
   int hash = Collections.secondaryHash(key); 计算出散列码
   HashMapEntry
             K eKey = e.key;
             if (eKey == key || (e.hash == hash && key.equals(eKey))) {
                 return e.value;
             }

•    若地址相同，返回值，
•    若hash值相等且equals返回true，返回值

5.总结

你几乎根本不用自己去实现散列表，因为你使用的编程语言提供了散列表实现。你可使用
java提供的散列表，并假定能够获得平均情况下的性能：常量时间。
散列表是一种功能强大的数据结构，其操作速度快，还能让你以不同的方式建立数据模型。
你可能很快会发现自己经常在使用它。
 你可以结合散列函数和数组来创建散列表。
 冲突很糟糕，你应使用可以最大限度减少冲突的散列函数。
 散列表的查找、插入和删除速度都非常快。
 散列表适合用于模拟映射关系。
 一旦填装因子超过0.7，就该调整散列表的长度。
 散列表可用于缓存数据（例如，在Web服务器上）。
 散列表非常适合用于防止重复。