数据结构之 哈希表

作者: 测试员 | 来源:发表于2019-08-27 20:45 被阅读0次

    google公司的一个上机题

    有一个公司,当有新的员工来报道时,要求将该员工的信息加入
    (id,名字...),当输入该员工的id时,要求查找到该员工的所有信息
    要求:
    不使用数据库,,速度越快越好=>哈希表(散列)添加时,保证按照id从低到高插入

    代码实现

    ps1:既然没有要求保证ID排列顺序 add方法就可以简单一些

    ps2:哈希表就是一个链表数组,CRUD方法主要是靠链表类的方法。

    package com.yuan.common.hashtab;
    
    
    public class HashTabDemo {
    
        public static void main(String[] args) {
            HashTable table = new HashTable();
            Emp emp_1 = new Emp(1, "qqq");
            Emp emp_2 = new Emp(2, "www");
            Emp emp_3 = new Emp(3, "eee");
            Emp emp_4 = new Emp(4, "rrr");
            Emp emp_5 = new Emp(112, "qqq");
            Emp emp_6 = new Emp(223, "www");
            Emp emp_7 = new Emp(334, "eee");
            Emp emp_8 = new Emp(445, "rrr");
            table.add(emp_1);
            table.add(emp_2);
            table.add(emp_3);
            table.add(emp_4);
            table.add(emp_5);
            table.add(emp_6);
            table.add(emp_7);
            table.add(emp_8);
            table.show();
        }
    }
    
    /**
     * 员工类
     */
    class Emp {
        /**
         * id
         */
        private int id;
        /**
         * 名字
         */
        private String name;
    
        /**
         * 节点信息
         */
        public Emp next;
    
        public Emp(int id, String name) {
            this.id = id;
            this.name = name;
        }
    
        public int getId() {
            return id;
        }
    
    
        public String getName() {
            return name;
        }
    
    }
    
    /**
     * 员工节点类【单向链表】
     */
    class EmpLinkedList {
        private Emp head;
    
        /**
         * 添加一个节点
         *
         * @param emp
         */
        public void add(Emp emp) {
            //如果的添加第一个成员
            if (head == null) {
                head = emp;
            } else {
                //否则
                Emp currentEmp = head;
                while (currentEmp.next != null) {
                    currentEmp = currentEmp.next;
                }
                currentEmp.next = emp;
            }
        }
    
        /**
         * 展示链表上的所有节点信息
         */
        public void show() {
            if (head == null) {
                System.out.println("没有数据");
            } else {
                Emp curEmp = head;
                while (curEmp != null) {
                    System.out.println(curEmp.getId() + "\t\t" + curEmp.getName());
                    curEmp = curEmp.next;
                }
            }
        }
    
        /**
         * 获取链表中有几个节点
         * @return
         */
        public int size() {
            if (head == null) {
                return 0;
            } else {
                int count = 0;
                Emp curEmp = head;
                while (curEmp != null) {
                    count++;
                    curEmp = curEmp.next;
                }
                return count;
            }
        }
    
    }
    
    /**
     * 员工哈希表
     */
    class HashTable {
        /**
         * 假设有5个链表最合理
         */
        private final int SIZE = 5;
        private EmpLinkedList[] empLinkedArray = new EmpLinkedList[SIZE];
    
        /**
         * 初始化要记得初始化数组,不然默认为null
         */
        public HashTable() {
            for (int x = 0; x < SIZE; x++) {
                empLinkedArray[x] = new EmpLinkedList();
            }
        }
    
        /**
         * 添加一个节点 调用的是链表方法
         *
         * @param emp
         */
        public void add(Emp emp) {
            int linkedNo = getLinkedNo(emp.getId());
            empLinkedArray[linkedNo].add(emp);
        }
    
        /**
         * id从零开始,一共5条单向链表
         *
         * @param id
         * @return
         */
        private int getLinkedNo(int id) {
            return id % SIZE;
        }
    
        public void show() {
            for (int i = 0; i < empLinkedArray.length; i++) {
                if (empLinkedArray[i].size() != 0) {
                    empLinkedArray[i].show();
                }
            }
        }
    }
    

    相关文章

      网友评论

        本文标题:数据结构之 哈希表

        本文链接:https://www.haomeiwen.com/subject/tzpyectx.html