哈希表

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

为什么要使用哈希表?首先我们来看下数组和链表的特点:

  • 数组:查询(寻址)易,操作(插入、删除)难。
  • 链表:查询(寻址)难,操作(插入、删除)易。

那我们能不能综合这两者的优点,创建一个查询(寻址)容易同时操作(插入、删除)也容易的数据结构?
答案就是哈希表,它能兼顾数组和链表的优点。

哈希表存储数据的结构图:

HashTable

该图左边是一个数组,每个数组存储内容指向一个链表。

散列函数

散列函数,能将一个元素根据该函数转换为哈希表的数组下表。

散列函数的常见实现方式:

  • 除法散列表,即将元素的关键码除以一个固定的数求摩。index = key % p
  • 平方散列法
  • 斐波那契散列法

下面代码用除法散列法的方式实现一个哈希表:

public class User {
    private int id;
    private String name;
    private User next;

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

    public int getId() { return id; }
    public void setId(int id) { this.id = id; }
    public String getName() { return name; }
    public void setName(String name) { this.name = name; }
    public User getNext() { return next; }
    public void setNext(User next) { this.next = next; }
    @Override
    public String toString() { return "User [id=" + id + ", name=" + name + "]"; }
}

public class UserLinkedList {
    private int index;    // 当前列表在哈希表中的索引
    private User head;    // 指向头结点

    public UserLinkedList(int index) {
        this.index = index;
        head = new User();
    }
    
    // 添加数据
    public void add(User user) {
        if(null == head.getNext()) {
            head.setNext(user);
            return ;
        }
        User tmp = head;
        while(null != tmp.getNext()) {
            tmp = tmp.getNext();
        }
        tmp.setNext(user);
    }
    
    // 查找数据
    public User find(int userId) {
        if(null == head.getNext()) {
            return null;
        }
        User result = null;
        User tmp = head.getNext();
        while(null != tmp) {
            if(userId == tmp.getId()) {
                result = tmp;
                break ;
            }
            tmp = tmp.getNext();
        }
        return result;
    }
    
    // 打印数据
    public void print() {
        if(null == head.getNext()) {
            System.err.printf("第%d条链表为空!\n", index + 1);
            return ;
        }
        System.out.printf("第%d条链表:", index + 1);
        User tmp = head.getNext();
        while(null != tmp) {
            System.out.print(tmp + "\t");
            tmp = tmp.getNext();
        }
        System.out.println();
    }
}

public class HashTable {
    private int size;
    private UserLinkedList[] userLinkedLists;
    public HashTable(int size) {
        super();
        this.size = size;
        this.userLinkedLists = new UserLinkedList[size];
        for(int i = 0; i < size; i++) {
            userLinkedLists[i] = new UserLinkedList(i);
        }
    }
    
    // 散列函数
    private int hash(int userId) {
        return userId % size;
    }
    
    // 添加数据
    public void add(User user) {
        int index = hash(user.getId());
        userLinkedLists[index].add(user);
    }
    
    // 查找数据
    public User find(int userId) {
        int index = hash(userId);
        return userLinkedLists[index].find(userId);
    }
    
    // 打印数据
    public void print() {
        for(int i = 0; i < size; i++) {
            userLinkedLists[i].print();
        }
    }
}

public class HashTableDemo {
    public static void main(String[] args) {
        HashTable hashTable = new HashTable(7);
        Scanner scanner = new Scanner(System.in);
        String key = null;
        boolean loop = true;
        while(loop) {
            System.out.println("a(add)添加数据");
            System.out.println("f(find)查找数据");
            System.out.println("p(print)打印数据");
            System.out.println("e(exit)退出");
            key = scanner.next();
            switch(key) {
                case "a":
                    System.out.println("请输入用户编号:");
                    int userId = scanner.nextInt();
                    System.out.println("请输入用户名称:");
                    String userName = scanner.next();
                    hashTable.add(new User(userId, userName));
                    break ;
                case "f":
                    System.out.println("请输入要查找的用户id");
                    int findVal = scanner.nextInt();
                    User findUser = hashTable.find(findVal);
                    if(null == findUser) {
                        System.err.printf("查找的用户id:%d不存在!\n", findVal);
                    } else {
                        System.out.println("查找的用户:" + findUser);
                    }
                    break ;
                case "p":
                    hashTable.print();
                    break ;
                case "e":
                    loop = false;
                    scanner.close();
                    break;
                default:
                    break;
            }
        }
    }
}

标签: 数据结构

添加新评论