散列表

什么是 散列表?

　散列表（Hash Table，即哈希表）是根据键值（Key）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表

为什么要有 散列表?

可以提供快速的插入操作和查找操作

　不论哈希表中有多少数据，插入和删除（有时包括侧除）只需要接近常量的时间即 O(1) 的时间级
　实际上，这只需要几条机器指令
　哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器），而树的操作通常需要 O(N) 的时间级

编程实现相对容易

散列表工作机制

存储

　使用一个数组实现的无序符号表
　意味着，数组创建后，难于扩展（某些哈希表被基本填满时，性能下降得非常严重）
　要么预设足够的空间，要么定期将数据迁移到更大的哈希表

查找

　首先，用散列函数将被查找的键转化为数组的一个索引
　其次，处理碰撞冲突

• 拉链法
  使用原始的链表数据类型来扩展 SequentialSerchT
  为 M 个元素分别构建符号表来保存散列到这里的键
• 线性探测法
  用大小为 M 的数组保存 N 个键值对（M > N, 依靠数组中空位解决碰撞冲突，此策略的所有方法统称为开放地址散列表）

散列表在 Java 中的相关实现：HashMap

java.lang.Object 的规范

• 如果一个对象的 equals 方法做比较所用到的信息没有被修改的话，那么，对该对象调用 hashCode 方法多次，必须始终如一地返回同一个整数
• 如果两个对象根据 equals(Object) 方法是相等，那么调用这两个对象中任意一个对象的 hashCode 方法必须产生同样的整数结果
• 对于不相等的对象产生截然不同的整数结果，有可能提高散列表的性能

HashMap 失效的情况

package com.yuzhouwan.hashCode2;

import java.util.HashMap;
import java.util.Map;

public final class PhoneNumber {
    private final short areaCode;
    private final short exchange;
    private final short extension;

    public PhoneNumber(int areaCode, int exchange, int extension) {
        rangeCheck(areaCode, 999, "area code");
        rangeCheck(exchange, 999, "exchange");
        rangeCheck(extension, 9999, "extension");
        this.areaCode = (short) areaCode;
        this.exchange = (short) exchange;
        this.extension = (short) extension;
    }

    private static void rangeCheck(int arg, int max, String name) {
        if (arg < 0 || arg > max)
            throw new IllegalArgumentException(name + ": " + arg);
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + areaCode;
        result = prime * result + exchange;
        result = prime * result + extension;
        return result;
    }

    /**
     * If u put the param that is not Object and forget use the annotation that name is 'Override',
     * the equals method loses efficacy and u will find the reason hardly.
     */
    @Override
    public boolean equals(Object o) {
        if (o == this) return true;
        if (!(o instanceof PhoneNumber)) return false;
        PhoneNumber pn = (PhoneNumber) o;
        return pn.extension == extension &&
                pn.exchange == exchange &&
                pn.areaCode == areaCode;
    }

    public boolean equals2(Object obj) {
        if (this == obj) return true;
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        PhoneNumber other = (PhoneNumber) obj;
        if (areaCode != other.areaCode) return false;
        if (exchange != other.exchange) return false;
        if (extension != other.extension) return false;
        return true;
    }

    /**
     * if u do not rewrite the hashCode method,
     * u will get the different hashCode when u init the same object, then the hashMap will work unusually.
     */
    public static void main(String... args) {
        Map<PhoneNumber, String> m = new HashMap<PhoneNumber, String>();

        PhoneNumber pn = new PhoneNumber(408, 867, 5309);
        m.put(pn, "Jenny");

        System.out.println("pn\' hashCode: " + pn.hashCode() + " - "
                + m.get(pn));

        pn = new PhoneNumber(408, 867, 5309);
        System.out.println("pn\' hashCode: " + pn.hashCode() + " - "
                + m.get(pn));
    }
}

　如果没有 hashCode 的结果：

pn hashCode: 909751202 - Jenny
pn hashCode: 104885374 - null

处方

　1. 把某个非零长数值，比如说 17，保存在一个叫 result 的 int 类型变量中
　2. 对于对象中每一个关键域 f（指 equals 方法中考虑的每个域），完成以下步骤：
　　a. 为该域计算 int 类型的散列码 c：

i. 如果该域是 boolean 类型，则计算 (f?0:1) 
ii. 如果该域是 byte、char、short 或者 int 类型，则计算  (int) f
iii. 如果该域是 long 类型，则计算 (int) (f ^ (f >>> 32)) 
iv. 如果该域是 float 类型，则计算 Float.floatToIntBits(f) 
v. 如果该域是 double 类型，则计算 Double.doubleToLongBits(f) 得到一个 long 类型的值，然后按照步骤 2.a.iii，对该 long 型值计算散列值
vi. 如果该域是一个对象引用，并且该类的 equals 方法通过递归调用 equals 的方式来比较这个域，则同样对这个域递归调用 hashCode
　如果要求一个更为复杂的比较，则为这个域计算一个 "规范表示（canonical representation）"，然后针对这个范式表示调用 hashCode
　如果这个域的值为 null，则返回 0（也可以设置为其他某个常数，但习惯上使用 0）
vii. 如果该域是一个数组，则把每一个元素当做单独的域来处理
　也就是说，递归地应用上述规则，对每个重要的元素计算一个散列码，然后根据步骤 2.b 中的做法把这些散列值组合起来

　　b. 按照下面的公式，把步骤 a 中计算得到的散列码 c 组合到 result 中：

result = 37 * result + c;

　3. 返回 result
　4. 写完了 hashCode 方法之后，问自己 “是否相等的实例具有相等的散列码”。如果不是的话，找出原因，并修改错误

冗余域（redundant field）

　如果一个域的值可以根据参与计算的其他域值计算出来，则把这样的域排除在外是可以接受的

ConcurrentHashMap 如何实现线程安全

　ConcurrentHashMap 中加了 lock 的方法（scanAndLockForPut、scanAndLock、lock 用来添加锁，并使用 try-finally 释放锁，以及使用 sun.misc.Unsafe 提供 volatile 变量）

+ java.util.concurrent.ConcurrentHashMap.Segment<K, V>
    - scanAndLockForPut  +  unclock
        put
    - scanAndLock        +  unclock
        remove、replace
    - lock               +  unclock
        clear
    - java.util.concurrent.locks.ReentrantLock.lock()  +  unlock()
        size、containsValue

+ java.util.concurrent.locks.ReentrantLock.lock() -> java.util.concurrent.locks.ReentrantLock.Sync.lock()
+ java.util.concurrent.locks.ReentrantLock.unlock() -> java.util.concurrent.locks.AbstractQueuedSynchronizer.release(int)
        writeObject(Serialization Support)

sun.misc.Unsafe.getObjectVolatile(Object, long)

get            // manually integrate access methods to reduce overhead
containsKey    // same as get() except no need for volatile value read

readObject 中读取流中所有的 Object

// Read the keys and values, and put the mappings in the table
for (;;) {                          // = while(true)
    K key = (K) s.readObject();     // java.io.ObjectInputStream
    V value = (V) s.readObject();
    if (key == null)
        break;                      // 只有达到这个条件，才可以退出这个死循环
    put(key, value);
}

欢迎加入我们的技术群，一起交流学习

群名称	群号
人工智能（高级）
人工智能（进阶）
BigData
算法