散列表的demo实现，二分查找

散列表，散列算法
[size=small]一、概念
首先，回顾下散列的概念。散列同顺序、链接和索引一样，是一中数据存储方法。
定义：以数据集合中的每个元素的关键字k为自变量，通过一个函数h(k)计算出函数值，用这个值作为一块连续的存储空间（数组或文件空间）中的元素存储位置，将该元素存放在这块位置上。其中h(k) 成为散列函数或哈希函数，而h(k)的值成为散列地址或者哈希地址。
散列表
根据散列函数计算出的值作为地址存放相关元素值，这样的一组数据存放方式称为散列表。
冲突
多个元素的key值计算出的哈希值为同一个时，就造成了冲突。通常来讲，这种具有不同关键字而具有相同散列地址的元素称为"同义词"，由同义词引起的存储冲突称为同义词冲突。

    发生冲突的因素：
        1、装填因子α，其中α=n/m，其中n为带插入的元素个数，m为散列表长度。一般来讲，α越小，发生冲突的可能性就越小，但是随之而来的问题是，空间利用率越低。
        2、散列函数的选择，若散列函数选择得当，就能使散列地址均匀的分布在散列空间上，从而减少冲突的发生。
        3、解决冲突的方法。
散列桶
   散列表（散列存储）中每个散列地址对应的存储位置被称为一个桶。

二、散列函数
1、直接定址法
   h(k) = k + C 其中k为关键字本身，C为常数。
   优点：简单，没有冲突发生，如果有冲突，则说明是关键字重复。
   缺点：若关键字不连续，空号较多，将造成存储空间的较大浪费。
2、除留取余数法
   h(k)=k%m
   该方法适用范围广，是目前最常见的方法。
3、其他
   数字分析法、平方取中法、折叠法

三、处理冲突的方法
    主要包含开放定址法（线性探查法、平方探查法、双散列函数探查法）、链接法（即链地址法）

    散列性能分析，从这本书《数据结构使用教程.徐孝凯》上得到的结果是链接地址法的平均查找长度是比较优秀的。
    
四、散列表的运算
    进行散列表的运算，首先定义散列表在Java中的接口类，说明该中存储结构需要有哪些功能，然后给出不同处理冲突方式的实现类。一般常用的有两种方式：一种是采用开放定址法处理；另一种是链接法处理冲突的实现类。

1、根据散列表的存储性质，定义接口类：

package com.algorithm.hash;

/**
 * 散列表的接口类
 * Created by xiaoyun on 2016/8/4.
 */
public interface HashTable {
    /**
     * 向散列表中插入一个关键字为theKey的元素obj，若插入成功返回真否则返回假
     * @param theKey
     * @param obj
     * @return
     */
    boolean insert(Object theKey, Object obj);

    /**
     * 从散列表中查找并返回与给定关键字theKey的元素值，若查找失败则返回假
     * @param theKey
     * @return
     */
    Object search(Object theKey);

    /**
     * 从散列表中删除关键字为theKey的元素，若查找失败返回空
     * @param theKey
     * @return
     */
    boolean delete(Object theKey);

    /**
     * 返回散列表中的元素个数
     * @return
     */
    int size();

    /**
     * 返回散列表的容量，即散列表的空间大小m的值
     * @return
     */
    int capacity();

    /**
     * 判断该散列表是否为空，如果为空则返回true，否则返回false
     * @return
     */
    boolean isEmpty();

    /**
     * 清空散列表
     */
    void clear();

    /**
     * 输出散列表中保存的所有关键字和对应元素
     */
    void output();
}

2、开放定址法处理冲突的数组存储类

package com.algorithm.hash;

/**
 * 采用开放定址法(这里采用线性探查法)处理冲突的数组存储类
 * Created by xiaoyun on 2016/8/4.
 */
public class SeqHashTable implements HashTable {

    /** 保存散列表的容量 */
    private int m;

    /** 定义保存元素关键字的数组 */
    private Object[] key;

    /** 定义保存散列桶的数组 */
    private Object[] ht;

    /** 散列表中已有的元素个数 */
    private int n;

    /** 元素内容被删除后的关键字删除标记 */
    private Object tag;

    /**
     * 私有方法-散列函数，假定采用除留取余数法，如果参数不是整数，应设法转换为整数
     * @param theKey
     * @return
     */
    private int h(Object theKey) {
        return (Integer)theKey % m;
    }

    /**
     * 构造方法
     * @param mm 散列表容量
     * @param tag 删除标记
     */
    public SeqHashTable(int mm, Object tag) {
        if(mm < 13) {
            this.m = 13; // 假定散列表的容量至少等于13
        }else {
            this.m = mm;
        }
        n = 0;
        key = new Object[m];
        ht = new Object[m];
        this.tag = tag;
    }

    /**
     * 向散列表中插入一个关键字为theKey的新元素obj,插入成功返回true，无可用空间直接退出
     * @param theKey
     * @param obj
     * @return
     */
    public boolean insert(Object theKey, Object obj) {
        int d = h(theKey);
        int temp = d;
        while(key[d] != null && !key[d].equals(this.tag)){
            if(key[d].equals(theKey)){
                break;
            }
            d = (d + 1)%m; // 探查下一个单元
            if(d == temp) {
                System.out.println("散列表无该元素的存储空间，退出运行！");
                System.exit(1);
            }
        }
        if(key[d] == null || key[d].equals(this.tag)) { // 找到插入位置，将该元素插入，返回true
            key[d] = theKey;
            ht[d] = obj;
            this.n++;
            return true;
        }else { // 用新元素obj替换已存在的元素并返回false
            ht[d] = obj;
            return false;
        }
    }

    /**
     * 从散列表中查找并返回与给定关键字theKey的元素值，若查找失败则返回假
     * @param theKey
     * @return
     */
    public Object search(Object theKey) {
        int d = h(theKey); // 求theKey的散列地址
        int temp = d; // 用temp暂存所求得的散列地址d
        while(key[d] != null) { // 当散列地址中的关键字不为空时进行循环
            if(key[d].equals(theKey)) {
                return ht[d];
            }else {
                d = (d + 1) % m;
            }
            if(d == temp) { // 查找一周后失败返回空值
                return null;
            }
        }
        return null;
    }

    /**
     * 从散列表中删除关键字为theKey的元素，若查找失败返回空
     * @param theKey
     * @return
     */
    public boolean delete(Object theKey) {
        int d = h(theKey);
        int temp = d;
        while (key[d] != null) { // 散列地址为空时退出循环
            if(key[d].equals(theKey)) { // 找到需要删除的元素
                key[d] = this.tag; // 设置删除标记
                ht[d] = null; // 元素值变为空
                n--; // 散列桶长度减一
                return true;
            } else {
                d = (d + 1) % m; // 线性探测法
            }
            if(d == temp) {
                return false;
            }
        }
        return false;
    }

    public int size() {
        return this.n;
    }

    public int capacity() {
        return this.m;
    }

    public boolean isEmpty() {
        return this.n == 0;
    }

    public void clear() {
        for (int i = 0; i < m; i++) {
            key[i] = null;
            ht[i] = null;
        }
        this.n = 0;
    }

    public void output() {
        for (int i = 0; i < m; i++) {
            if(key[i] == null || key[i].equals(tag)){
                continue;
            }
            System.out.print("(" + key[i] + " " + ht[i] + "),");
        }
        System.out.println();
    }
}

3、采用链接法处理冲突的链接存储类
定义结点类型

package com.algorithm.hash;

/**
 * 链地址法处理冲突的散列表中的结点类型
 * Created by xiaoyun on 2016/8/6.
 */
public class HashNode {
    Object key;
    Object element;
    HashNode next;
    public HashNode(Object key, Object element) {
        this.key = key;
        this.element = element;
        next = null;
    }
}

定义存储结构：

package com.algorithm.hash;

/**
 * 链接法处理冲突的散列表
 * Created by xiaoyun on 2016/8/6.
 */
public class LinkHashTable implements HashTable {

    private int m; // 保存散列表的容量

    private HashNode[] ht; // 定义保存散列表的数组

    private int n; // 散列表中已有元素的个数

    /**
     * 定义散列函数，除留取余数法
     * @param key
     * @return
     */
    private int h(Object key) {
        return (Integer)key%this.m;
    }

    public LinkHashTable(int m) {
        if(m < 13) {
            this.m = 13;
        }else {
            this.m = m;
        }
        n = 0;
        ht = new HashNode[this.m];
    }

    /**
     * 向散列表中插入一个关键字为theKey的元素obj，若插入成功返回真否则返回假
     * @param theKey
     * @param obj
     * @return
     */
    public boolean insert(Object theKey, Object obj) {
        int d = h(theKey);
        HashNode p = ht[d];
        while (p != null) {
            if(p.key.equals(theKey)){
                break;
            }else {
                p = p.next;
            }
        }
        if(p != null) { // 用新值替换旧值，返回false
            p.element = obj;
            return false;
        }else { // 将新结点插入到对应单链表的表头并返回真
            p = new HashNode(theKey, obj);
            p.next = ht[d];
            ht[d] = p;
            n++;
            return true;
        }
    }

    /**
     * 从散列表中查找并返回与给定关键字theKey的元素值，若查找失败则返回假
     * @param theKey
     * @return
     */
    public Object search(Object theKey) {
        int d = h(theKey);
        HashNode p = ht[d];
        while (p != null) {
            if(p.key.equals(theKey)){
                return p.element;
            }
            p = p.next;
        }
        return null;
    }

    public boolean delete(Object theKey) {
        int d = h(theKey);
        HashNode p = ht[d]; // p指向表头结点
        HashNode q = null; // q指向前驱结点
        while (p != null) { // 循环查找被删除的结点
            if(p.key.equals(theKey)){
                break;
            }else {
                q = p;
                p = p.next;
            }
        }
        if(p == null){
            return false;
        }
        if(q == null) {
            ht[d] = p.next;
        }else {
            q.next = p.next;
        }
        n--;
        return true;
    }

    public int size() {
        return this.n;
    }

    public int capacity() {
        return this.m;
    }

    public boolean isEmpty() {
        return this.n == 0;
    }

    public void clear() {
        for (int i = 0; i < m; i++) {
            ht[i] = null;
        }
        n = 0;
    }

    public void output() {
        for (int i = 0; i < m; i++) {
            HashNode p = ht[i];
            while(p != null) {
                System.out.print("(" + p.key +":" + p.element+"),");
                p = p.next;
            }
        }
        System.out.println();
    }
}

4、散列表运算的调试程序

import com.algorithm.hash.HashTable;
import com.algorithm.hash.LinkHashTable;
import com.algorithm.hash.SeqHashTable;

/**
 * 散列表算法测试类
 * Created by admin on 2016/8/6.
 */
public class Example10_3 {
    public static void main(String[] args) {
        // 关键字数组
        int[] a = {18,75,60,43,54,90,46,31,58,73,15,34};
        // 要存放的元素数组
        String[] b = {"180","750","600","430", "540", "900","460","310","580","730","150","340"};
        // 初始化开放地址法处理冲突的散列表
        //HashTable tb = new SeqHashTable(17, -1);
        // 链地址法处理冲突的散列表
        HashTable tb = new LinkHashTable(17);
        for (int i = 0; i < a.length; i++) {
            tb.insert(a[i], b[i]);
        }
        System.out.println("输出散列表中的所有元素：");
        tb.output();
        System.out.println("散列表容量：" + tb.capacity());
        System.out.println("散列表中的元素个数：" + tb.size());
        // 删除元素
        for (int i = 0; i < a.length; i += 3) {
            tb.delete(a[i]);
        }
        // 修改元素
        tb.insert(75, "880");
        System.out.println("经插入、删除、修改后的散列表为：");
        tb.output();
        System.out.println("散列表容量：" + tb.capacity());
        System.out.println("散列表中的元素个数：" + tb.size());
        System.out.println("查找元素的结果：");
        for (int i = 0; i < 4; i++) {
            Object x = tb.search(a[i]);
            if(x == null) {
                System.out.println("key为 " + a[i] + "关键字的元素未找到！");
            }else {
                System.out.println("key为 " + a[i] + "对应的元素值为：" + x);
            }
        }
    }
}

运行结果：
输出散列表中的所有元素：
(34:340),(18:180),(54:540),(73:730),(90:900),(58:580),(75:750),(43:430),(60:600),(46:460),(31:310),(15:150),
散列表容量：17
散列表中的元素个数：12
经插入、删除、修改后的散列表为：
(34:340),(54:540),(90:900),(58:580),(75:880),(60:600),(31:310),(15:150),
散列表容量：17
散列表中的元素个数：8
查找元素的结果：
key为 18关键字的元素未找到！
key为 75对应的元素值为：880
key为 60对应的元素值为：600
key为 43关键字的元素未找到！

以上为使用链接法处理冲突的算法调试结果。
将Example10_3.java的18行注释掉，去掉16行的注释，则为测试开放定址法的数组存储类，执行结果为：
输出散列表中的所有元素：
(34 340),(18 180),(54 540),(90 900),(73 730),(75 750),(58 580),(60 600),(43 430),(46 460),(31 310),(15 150),
散列表容量：17
散列表中的元素个数：12
经插入、删除、修改后的散列表为：
(34 340),(54 540),(90 900),(75 880),(58 580),(60 600),(31 310),(15 150),
散列表容量：17
散列表中的元素个数：8
查找元素的结果：
key为 18关键字的元素未找到！
key为 75对应的元素值为：880
key为 60对应的元素值为：600
key为 43关键字的元素未找到！
[/size]

二分查找
定义：二分查找又称为折半查找，是一种能对有序表进行快速查找的方法，时间复杂度为O(log₂N)。

package com.data.search.binary;

/**
 * 二分查找算法
 * 二分查找定义：二分查找又称为折半查找，首先，二分查找是针对有序表a（这里认为是升序）进行查找，首先取数组中的中间值a[mid]，同给定的值x进行比较，如果x小于中间值，那么max=mid-1,min=0,mid=(max-min)/2,
 *               继续比较a[mid]与x的大小，然后依次递归，直到找到对应的元素或者查找区间为空为止。
 * Created by xiaoyun on 2016/8/1.
 */
public class BinarySearch {
    /**
     * 从数组的前n个元素中二分查找值为x的元素
     * @param a
     * @param x
     * @param n
     * @return
     * 时间复杂度：二分查找过程可用一棵二叉树来描述，它的左子树和右子树分别代码对应区间的左子表和右子表，通常把这样的二叉树称为判定树，
     *             进行二分查找的判定树不仅是一棵二叉搜索树，而且是一颗理想二叉树，因为除了最后一层外，其余所有层的结点数都是满的。
     *             所以二分查找的时间复杂度为：O(log₂N),其中N为元素个数。
     * 优点：比较次数少，查找速度快。
     * 缺点：查找前需要建立有序表，这需要付出一定代价，同时对该有序表进行插入和删除操作都需要平均比较和移动表中的一半元素，是浪费时间的操作。
     * 应用场景：适用于顺序存储、并且不经常进行插入和删除的有序表。不适用于链接存储的有序表。
     */
    public static int binarySearch(Object[] a, Object x, int n) {
        int low = 0;
        int high = n - 1;
        while(low <= high) {
            int mid = (low + high)/2;
            // 比较该下标代表的值与目标值
            int result = ((Comparable)a[mid]).compareTo(x);
            if(result == 0) {
                return mid;
            }else if(result > 0) { // 查找左区间
                high = mid  - 1;
            }else { // 查找右区间
                low = mid + 1;
            }
        }
        return -1; // 查找失败返回-1
    }

    public static void main(String[] args) {
        Object[] a = {1,2,3,4,5,6,7,8,9,10,11};
        System.out.println(binarySearch(a, 5, 5));
    }
}

优点：比较次数少，查找速度快。
缺点：查找前需要建立有序表，而频繁的插入和删除平均每次需要移动表中的一半元素，浪费时间。
适用场景：数据稳定，很少进行插入或删除运算的情况。也就是说，二分查找只适用于顺序存储的有序表，不适于连接存储的有序表。