数据结构与算法（十八）哈希表(散列)

基本介绍：

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

案例分析

看一个实际需求，google公司的一个上机题:

有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址..),当输入该员工的id时,要求查找到该员工的 所有信息.

要求: 不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)

代码实现

员工信息

/**
 * 员工信息
 */
class Emp{

    public  int id;
    public String name;
    public  Emp next;
    public Emp(int id ,String name){
        this.id=id;
        this.name=name;
    }
}

链表信息

class LinkedList{
    private Emp head;

    /**
     * 增加
     * @param emp
     */
    public void add(Emp emp){
        if (head == null){
            head=emp;
            return;
        }
        Emp cur=head;
        while (true){
            if (cur.next == null){
                break;
            }
            cur=cur.next;
        }
        cur.next=emp;
    }

    /**
     * 查找
     * @param id
     * @return
     */
    public int  search(int id){
        if (head == null){
            return -1;
        }
        Emp cur=head;
        while (true){
            if (cur.id == id){
                return id;
            }
            if (cur.next == null){
                break;
            }
            cur=cur.next;
        }
        return -1;
    }


    /**
     * 遍历
     */
    public void list(int i){
        if (head == null){
         System.out.println("链表"+i+"没有数据");
         return;
        }
        Emp cur=head;
        while (true){
            System.out.printf("==>id=%d,name=%s \t",cur.id,cur.name);
            if (cur.next == null){
                break;
            }
            cur=cur.next;
        }
        System.out.println();
    }


}

哈希表

public class HashTable {

    private LinkedList [] linkedLists;


    private int size;

    public HashTable(int size){
        this.size=size;
        linkedLists=new LinkedList[size];
        for (int i=0;i<size;i++){
            linkedLists[i]=new LinkedList();
        }
    }


    /**
     * 增加
     * @param emp
     */
    public void add(Emp emp){
        int hash = hash(emp.id);
        linkedLists[hash].add(emp);
    }

    /**
     * 展示
     */
    public void list(){
        for (int i=0;i<size;i++){
            linkedLists[i].list(i+1);
        }
    }

    /**
     * 根据id 查询
     * @param id
     * @return
     */
    public int search(int id){
        int hash = hash(id);
        return linkedLists[hash].search(id);
    }




    public int hash(int id){
        return id % size;
    }


}

我们来测试下

public static void main(String[] args) {
        HashTable hashTable=new HashTable(3);
        String key="";
        Scanner scanner=new Scanner(System.in);
        while (true){
            System.out.println("add : 增加员工");
            System.out.println("list : 显示员工");
            System.out.println("search : 查询员工");
            System.out.println("exit : 退出系统");

            System.out.println("请输入：");
             key = scanner.next();
            switch (key){
                case "add":
                    System.out.println("请输入id：");
                    int id=scanner.nextInt();
                    System.out.println("请输入姓名：");
                    String name=scanner.next();
                    hashTable.add(new Emp(id,name));
                    break;
                case "list":
                    hashTable.list();
                    break;
                case "search":
                    System.out.println("请输入id：");
                     id=scanner.nextInt();
                     int index=hashTable.search(id);
                     if (index ==-1){
                         System.out.println("没有找到");
                     }else {
                         System.out.printf("找到id=%d\n",id);
                     }
                     break;
                case  "exit":
                    scanner.close();
                    System.exit(0);
                    break;
                default:
                    break;
            }

        }



    }