精华内容
下载资源
问答
  • 哈希表(散列)

    2020-07-18 20:28:24
    1,哈希表基本介绍 散列表(HashTable,也叫哈希表),是根据关键码值(Key Value)而进行访问的数据结构。...2,哈希表示意图 3,哈希表代码实现 package com.self.datastructure.hash; import

    1,哈希表基本介绍

    • 散列表(HashTable,也叫哈希表),是根据关键码值(Key Value)而进行访问的数据结构。也就是说,通过关键码值映射到表中的一个位置来访问记录,以加快查找的速度。这个映射函数叫散列函数,存放记录的数组叫做散列表
    • 基本数据结构为 数组 + 链表;通过键值获取到数组索引位置,存储到数组中,数组中该索引位置如果已经存在数据,则在该索引位置上构造链表。

    2,哈希表示意图

    在这里插入图片描述

    3,哈希表代码实现

    package com.self.datastructure.hash;
    
    import lombok.Data;
    import lombok.ToString;
    
    import java.util.Scanner;
    import java.util.UUID;
    
    /**
     * 自定义哈希表进行数据存储和查找
     * 也就是写一个简单的HashMap, 没有扩容和树转换逻辑
     *
     * @author PJ_ZHANG
     * @create 2020-03-18 17:53
     **/
    public class MyHashTable {
    
        public static void main(String[] args) {
            SelfHash selfHash = new SelfHash();
            for (int i = 0; i < 100; i++) {
                selfHash.put(i + "", new Employee(i + "name", i + ""));
            }
            System.out.println("总数: " + selfHash.size());
            for (;;) {
                System.out.println("输入要删除的元素编号");
                Scanner scanner = new Scanner(System.in);
                String inputId = scanner.nextLine();
                System.out.println(selfHash.get(inputId));
                System.out.println(selfHash.remove(inputId));
                System.out.println(selfHash.get(inputId));
            }
        }
    
        /**
         * 哈希列表类, 进行数据操作
         * Node[] 数组
         * Node自身为链表
         * 整体数据结构为数组+链表
         */
        static class SelfHash {
    
            // 默认长度
            private static int DEFAULT_SIZE = 16;
    
            // 初始化长度
            private static int length = DEFAULT_SIZE;
    
            // 元素数量
            private static int size;
    
            // 数组
            // 数组中的每一个元素为链表
            private Node[] nodeArray;
    
            public SelfHash() {
                this(length);
            }
    
            public SelfHash(int size) {
                this.length = size;
                nodeArray = new Node[this.length];
            }
    
            /**
             * 存数据/改数据
             * @param key
             * @param value
             */
            public void put(String key, Employee value) {
                if (nodeArray == null) nodeArray = new Node[DEFAULT_SIZE];
                // 获取对应存储下标
                int targetIndex = key.hashCode() % length;
                // 为空, 说明元素不存在
                if (null == nodeArray[targetIndex]) {
                    nodeArray[targetIndex] = new Node(key, value);
                    size++;
                } else {
                    // 获取到当前链表, 并获取链表最后一个元素
                    Node node = nodeArray[targetIndex];
                    Node preNode = node;
                    for (;node != null;) {
                        if (node.getKey().equals(key)) {
                            node.setValue(value);
                            return;
                        }
                        preNode = node;
                        node = node.getNextNode();
                    }
                    // node为空, preNode表示最后一个元素
                    // 将当前元素挂到该位置
                    preNode.setNextNode(new Node(key, value));
                    size++;
                }
            }
    
            /**
             * 取数据
             * @param key
             */
            public Employee get(String key) {
                int targetIndex = key.hashCode() % length;
                Node node = nodeArray[targetIndex];
                for (;null != node;) {
                    if (key.equals(node.getKey())) {
                        return node.getValue();
                    }
                    node = node.getNextNode();
                }
                return null;
            }
    
            /**
             * 移除数据
             * @param key
             */
            public boolean remove(String key) {
                int targetIndex = key.hashCode() % length;
                Node node = nodeArray[targetIndex];
                Node preNode = node;
                for (;null != node;) {
                    if (key.equals(node.getKey())) {
                        // 头结点, 当数组元素设置为下一个节点
                        if (preNode == node) {
                            nodeArray[targetIndex] = node.getNextNode();
                        } else { // 非头节点, 挂空当前节点
                            preNode.setNextNode(node.getNextNode());
                        }
                        return true;
                    }
                    preNode = node;
                    node = node.getNextNode();
                }
                return false; // 移除失败
            }
    
            /**
             * 列表展示
             */
            public void showArray() {
                if (size == 0) {
                    System.out.println("数据为空...");
                    return;
                }
                for (int i = 0; i < length; i++) {
                    Node node = nodeArray[i];
                    for (;null != node;) {
                        System.out.println("Node: INDEX: " + i + ", " + node.getValue());
                        node = node.getNextNode();
                    }
                }
            }
    
            public int size() {
                return size;
            }
    
            /**
             * 获取数组长度
             * @return
             */
            public int length() {
                return length;
            }
    
        }
    
        /**
         * 自定义Node
         * 存储键值对信息,
         * 存储链表信心
         */
        @Data
        static class Node {
    
            private String key;
    
            private Employee value;
    
            private Node nextNode;
    
            public Node() {}
    
            public Node(String key, Employee value) {
                this(key, value, null);
            }
    
            public Node(String key, Employee value, Node nextNode) {
                this.key = key;
                this.value = value;
                this.nextNode = nextNode;
            }
    
        }
    
        /**
         * 员工类, 实体数据
         * 存储到数据表时, 基本格式为{id, Employee}
         */
        @Data
        @ToString
        static class Employee {
    
            String id;
    
            String name;
    
            public Employee() {}
    
            public Employee(String name) {
                this(UUID.randomUUID().toString().replaceAll("-", ""), name);
            }
    
            public Employee(String id, String name) {
                this.id = id;
                this.name = name;
            }
    
        }
    
    }
    
    展开全文
  • 哈希表

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

    哈希表

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

    哈希表 = 数组 + 链表

    哈希表 = 数组 + 二叉树

    google 公司的一个上机题

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

    要求:

    1) 不使用数据库,速度越快越好=>哈希表(散列);

    2) 添加时, id 不是从低到高插入(无序),但要求各条链表仍是从低到高(有序);

    3) 使用链表来实现哈希表, 该链表不带表头[即: 链表的第一个结点就存放雇员信息] ;

    4) 思路分析并画出示意图 

    代码实现:

    数组 + 单链表(不带头节点)

    package com.hashtab;
    
    import java.util.Scanner;
    
    /**
     * @program: DataStructures
     * @description: 哈希表
     * @author: XuDeming
     * @date: 2019-12-31 20:57:54
     **/
    public class HashTableDemo {
        public static void main(String[] args) {
    
            // 创建哈希表
            HashTab hashTab = new HashTab(7);
    
            Scanner scanner = new Scanner(System.in);
            boolean flag = true;
            while (flag) {
                System.out.println("***雇员操作菜单***");
                System.out.println("a(add): 添加雇员信息");
                System.out.println("l(list): 显示雇员信息");
                System.out.println("f(find): 查找雇员信息");
                System.out.println("u(update): 更新雇员信息");
                System.out.println("d(delete): 删除雇员信息");
                System.out.println("e(exit): 退出系统");
                System.out.println("请输入操作字符:");
    
                char key = scanner.next().charAt(0);
                int id;
                String name;
                switch (key) {
                    case 'a':
                        System.out.println("请输入雇员编号");
                        id = scanner.nextInt();
                        System.out.println("请输入雇员姓名");
                        name = scanner.next();
                        hashTab.add(new Emp(id, name));
                        break;
                    case 'l':
                        hashTab.list();
                        break;
                    case 'f':
                        System.out.println("请输入要查找的雇员编号");
                        id = scanner.nextInt();
                        hashTab.findEmpById(id);
                        break;
                    case 'u':
                        System.out.println("请输入要更新的雇员编号");
                        id = scanner.nextInt();
                        System.out.println("请输入要更新的雇员姓名");
                        name = scanner.next();
                        hashTab.updateEmpById(id, name);
                        break;
                    case 'd':
                        System.out.println("请输入要删除的雇员编号");
                        id = scanner.nextInt();
                        hashTab.deleteEmpById(id);
                        break;
                    case 'e':
                        flag = false;
                        break;
                    default:
                        System.out.println("输入有误请重输");
                        break;
                }
            }
        }
    }
    
    // 表示一个雇员
    class Emp {
    
        public int id;// 编号
        public String name;// 姓名
        public Emp next;// 指向下一个节点
    
        public Emp(int id, String name) {
            this.id = id;
            this.name = name;
        }
    
        @Override
        public String toString() {
            return "{" +
                    "id=" + id +
                    ", name='" + name + '\'' +
                    '}';
        }
    }
    
    // 创建一个链表(不带头节点)
    class EmpLinkedList {
    
        // 第一个节点
        private Emp head;
    
        /**
         * 添加一个雇员 (乱序添加,链表有序)
         * @param emp 新雇员
         */
        public void add(Emp emp) {
            // 空链表
            if (head == null) {
                head = emp;
                return;
            }
            // 非空
            Emp empById = findEmpById(emp.id);
            if (empById == null) {// 该编号未被占用
                Emp temp = head;// 辅助指针
                if (emp.id < head.id) {// 1.添加节点编号比头节点小 添加节点作为头节点
                    emp.next = temp;
                    head = emp;
                } else {
                    while (temp.next != null) {// 寻找最后一个节点
                        temp = temp.next;
                    }
                    if (temp.id > emp.id) {// 如果最后一个节点编号比添加节点大 就将该节点放到第一个节点与最后一个节点之间
                        temp = head;
                        while (!(temp.id < emp.id && emp.id < temp.next.id)) {// 寻找插入位置的前一个节点
                            temp = temp.next;
                        }
                        emp.next = temp.next;
                    }
                    temp.next = emp;
                }
            } else {
                System.out.println("该编号已被占用");
            }
        }
    
        /**
         * 遍历该编号链表的雇员信息
         * @param no 链表编号
         */
        public void list(int no) {
            // 空链表
            if (head == null) {
                System.out.println("第 " + (no + 1) + " 号链表为空");
                return;
            }
            System.out.print("第 " + (no + 1) + " 号链表的信息为:");
            Emp temp = head;
            while (true) {
                System.out.print(temp + "\t");
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            System.out.println();
        }
    
        /**
         * 根据id查找雇员
         * @param id 雇员id
         * @return 找到返回雇员对象 找不到返回null
         */
        public Emp findEmpById(int id) {
            // 空链表
            if (head == null) {
                System.out.println("链表为空");
                return null;
            }
            Emp temp = head;
            while (temp != null) {
                if (temp.id == id) {
                    return temp;
                }
                temp = temp.next;
            }
            return null;
        }
    
        /**
         * 根据id更新雇员信息
         * @param id 雇员编号
         * @param name 更新的信息
         */
        public void updateEmpById(int id, String name) {
            Emp emp = findEmpById(id);
            if (emp == null) {
                System.out.println("修改信息失败");
                return;
            }
            emp.name = name;
        }
    
        /**
         * 根据id删除雇员信息
         * @param id 雇员id
         */
        public void deleteEmpById(int id) {
            Emp emp = findEmpById(id);
            if (emp == null) {
                System.out.println("删除信息失败");
                return;
            }
    
            // 判断删除节点的位置
            // 删除节点是头节点
            if (emp == head) {
                head = head.next;
                return;
            }
            Emp temp = head;
            // 删除节点是尾节点
            if (emp.next == null) {// 在链表最后
                while (temp.next.next != null) {// 寻找删除节点的上一个节点
                    temp = temp.next;
                }
                temp.next = null;
            } else {// 删除节点是中间节点
                while (temp.next.id != id) {// 寻找删除节点的上一个节点
                    temp = temp.next;
                }
                temp.next = temp.next.next;
            }
        }
    
    }
    
    // 创建HashTab管理多条链表
    class HashTab {
    
        // 哈希表
        private EmpLinkedList[] empLinkedListArray;
    
        // 表示链表的条数
        private int size;
    
        public HashTab(int size) {
            this.size = size;
    
            // 初始化
            empLinkedListArray = new EmpLinkedList[size];
    
            // 初始化数组中的每一条链表******
            for (int i = 0; i < size; i++) {
                empLinkedListArray[i] = new EmpLinkedList();
            }
        }
    
        /**
         * 向哈希表中添加元素(添加雇员)
         * @param emp 雇员对象
         */
        public void add(Emp emp) {
            // 查找雇员添加的链表
            int no = hashFun(emp.id);
            // 将雇员添加到对应的链表中
            empLinkedListArray[no].add(emp);
        }
    
        /**
         * 哈希函数 - 哈希取模
         * @param id 雇员编号
         * @return 返回数组下标值 即哪一条链表
         */
        private int hashFun(int id) {
            return id % size;
        }
    
        /**
         * 遍历所有链表
         */
        public void list() {
            for (int i = 0; i < size; i++) {
                empLinkedListArray[i].list(i);
            }
        }
    
        /**
         * 根据雇员id查找雇员信息
         * @param id 雇员id
         */
        public void findEmpById(int id) {
            // 根据雇员id查找对应存储的链表
            int no = hashFun(id);
            Emp emp = empLinkedListArray[no].findEmpById(id);
            if (emp != null) {
                System.out.println("在第 " + (no + 1) + " 号链表上找到雇员信息:" + emp);
            } else {
                System.out.println("无该编号雇员");
            }
        }
    
        /**
         * 根据雇员id删除雇员信息
         * @param id 雇员id
         */
        public void deleteEmpById(int id) {
            // 根据雇员id查找对应存储的链表
            int no = hashFun(id);
            empLinkedListArray[no].deleteEmpById(id);
        }
    
        /**
         * 根据雇员id更新雇员信息
         * @param id 雇员id
         * @param name 更新的信息
         */
        public void updateEmpById(int id, String name) {
            // 根据雇员id查找对应存储的链表
            int no = hashFun(id);
            empLinkedListArray[no].updateEmpById(id, name);
        }
    
    }
    

     

     

    展开全文
  • 哈希表实现

    2020-07-27 08:47:29
    哈希表哈希表的介绍和内存布局哈希表的图解,哈希表实现 案例案例思路图解 哈希表的介绍和内存布局 先看一个实际需求,google公司的一个上机题: 有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,...

    1、哈希表的介绍和内存布局

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

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

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

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

    2、哈希表的图解,

    通过数组+链表的方式来快速访问。(java里的hashMap)
    在这里插入图片描述
    所以什么叫哈希表?

    哈希表可以用来高效率解决元素不可重复这个问题,其本质就是:数组+链表+红黑树在这里插入图片描述

    3、哈希表实现 案例

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

    要求

    1. :不使用数据库,速度越快越好 => 哈希表(散列).
    2. 添加时,保证按照id从低到高插入, [课后思考:如果id不是从低到高插入,但要求各条链表仍是从低到高,怎么解决?]
    3. 使用链表来实现哈希表,该链表不带表头[即:链表的第一个结点就存放雇员信息]
    4. 思路分析并画出示意图

    4、案例思路图解

    使用哈希表来管理雇员信息
    在这里插入图片描述

    5、代码实现

    • 员工类
    //员工  代表链表上的节点
    class Emp {
        public int id;
        public String name;
        public Emp next; //next 默认为null
    
        public Emp(){}
        public Emp(int id, String name) {
            this.id = id;
            this.name = name;
        }
    
        @Override
        public String toString() {
            return "Emp{" +
                    "id=" + id +
                    ", name='" + name + '\'' +
                    '}';
        }
    }
    
    • EmpLinkedList
    //创建EmpLinkedList 表示链表
    class EmpLinkedList{
        //头指针,执行第一个Emp,因那次我们这个链表的head直接指向第一个Emp
        public Emp head; //默认为null
    
        //添加员工到链表
        public void addEmp(Emp emp){
            if(head == null){
                head = emp;
                return;
            }
            //不能添加已有id员工
            Emp findEmp = findEmp(emp.id);
            if(findEmp != null){
                System.out.println("已存在id= "+findEmp.toString()+"的员工,不能添加重复id员工"+emp.toString());
                return;
            }
            //不是第一个员工,定义一个辅助指针
            Emp curTemp = head;
            while(curTemp.next != null){
                curTemp = curTemp.next;//后移
            }
            //退出时将emp加入链表
            curTemp.next = emp;
    
        }
    
        //按id从小到大 添加员工到链表
        public void addEmpById(Emp emp){
            if(head == null){
                head = emp;
                return;
            }
            //不能添加已有id员工
            Emp findEmp = findEmp(emp.id);
            if(findEmp != null){
                System.out.println("已存在id= "+findEmp.toString()+"的员工,不能添加重复id员工"+emp.toString());
                return;
            }
            //如果新加结点比头节点小
            if(head.id > emp.id){
                Emp temp = null;
                emp.next = head;
                temp = head;
                head = emp;
                return;
            }
            
            //定义一个辅助指针
            Emp curTemp = head;
            while( true){
                //遍历到末尾还未找到,添加
                if(curTemp.next == null &&curTemp.id < emp.id){
                    curTemp.next = emp;
                    break;
                }
               
                if(curTemp.next.id > emp.id){
                    emp.next = curTemp.next;
                    curTemp.next = emp;
                    break;
                }
                curTemp = curTemp.next;
    
            }
    
        }
    
        //遍历链表
        public void list(int index){
            if(head == null){
                System.out.println("第"+(index+1)+"链表为空。");
                return;
            }
    
            Emp curTemp = head; //辅助指针
            System.out.println("第"+(index+1)+"链表信息如下:");
            while(curTemp != null){
                System.out.println(curTemp.toString());
                curTemp = curTemp.next;
            }
        }
    
        //从链表删除员工
        //链表删除需要找到删除结点的前一个节点,因此分为第一个节点和第2-n结点判断
        public void delete( int id){
            if(head == null){
                System.out.println("当前链表为空。");
                return;
            }
            //头节点直接删除
            if(head.id == id){
                head = head.next;
                System.out.println("Id为" + id + "的员工已经被删除~~");
                return;
            }
            Emp curTemp = head; //辅助指针
            while (true){
                if(curTemp.next == null ){
                    break;
                }
    
                if( curTemp.next.id == id){
                    curTemp.next = curTemp.next.next;
                    System.out.println("Id为" + id + "的员工已经被删除~~");
                    return;//删除之后直接退出,否则还会向下执行
                }
    
                curTemp =curTemp.next;
    
            }
        }
    
        //修改员工信息
        public void update( Emp emp){
            if(head == null){
                System.out.println("当前链表为空。");
                return;
            }
            Emp findEmp = findEmp(emp.id);
            if(findEmp == null){
                System.out.println("未找到id = "+emp.id+"员工信息");
                return;
            }
            Emp curTemp = head; //辅助指针
            while (true){
              
                if(curTemp == null ){
                    break;
                }
                if( curTemp.id == emp.id){
                    curTemp.name = emp.name;
                    return;//跟新之后直接退出,否则还会向下执行
                }
                curTemp =curTemp.next;
    
    
            }
        }
    
        //查找员工
        public Emp findEmp( int id){
            if(head == null){
                System.out.println("当前链表为空。");
                return null;
            }
            Emp curTemp = head; //辅助指针
           
    
            while (curTemp != null){
                if( curTemp.id == id){
                    //System.out.println(curTemp.toString());
                    return curTemp;
                }
                curTemp =curTemp.next;
            }
    
            return null;
        }
        //根据id查询雇员
        //如果查找到,就返回Emp,没有找到,就返回null
        public Emp findEmpId(int id){
            //判断链表是否为空
            if(head == null){
                System.out.println("链表为空.");
                return null;
            }
            //辅助指针
            Emp curEmp = head;
            while(true){
                if(curEmp.id == id){	//找到
                    break;	//此时curEmp就指向要查找的雇员
                }
                //退出
                if(curEmp.next == null){	//未找到该雇员
                    curEmp = null;
                    break;
                }
                curEmp = curEmp.next;	//后移
            }
            return curEmp;
        }
    }
    
    • HashTable
    //创建HashTable 管理多条链表
    class HashTable{
        private EmpLinkedList[] LinkedList;
        private int size ;//表示共有多少条链表
    
        public HashTable(int size){
            this.size = size;
            //初始化LinkedList
            LinkedList = new EmpLinkedList[size];
            //还未初始化 null , 分别为每个链表初始化
            for (int i = 0; i < size; i++) {
                LinkedList[i] = new EmpLinkedList();
            }
        }
    
        //添加雇员
        public void add(Emp emp){
            //根据员工id,找到员工应该在哪条链表下
            int LinkedListIndex = hashFun(emp.id);
            //将emp 添加到对应的链表中
    		// LinkedList[LinkedListIndex].addEmp(emp);
    		//按id大小进行排序
            LinkedList[LinkedListIndex].addEmpById(emp);
        }
    
        //遍历哈希表
        public void list(){
            for (int i = 0; i < size; i++) {
                LinkedList[i].list(i);
            }
        }
    
        public void findEmpId(int id){
            //得到该员工id在hashtable上那个角标
            int index = hashFun(id);
            //进入该链表查找员工
            Emp emp = LinkedList[index].findEmp(id);
            if(emp == null){
                System.out.println("未找到");;//表示遍历完,还未找到该节点 返回null
            }else{
                System.out.println(emp.toString());
            }
        }
        public void delEmpId(int id){
            //得到该员工id在hashtable上那个角标
            int index = hashFun(id);
            //进入该链表查找员工
            LinkedList[index].delete(id);
        }
    
        public void updateEmp(Emp emp){
            int index = hashFun(emp.id);
            //进入该链表查找员工
            LinkedList[index].update(emp);
        }
        //编写一个散列函数,使用取模法
        public int hashFun(int id){
            return id % size;
        }
    }
    
    • Demo测试
    public class HashTableDemo {
        public static void main(String[] args) {
            //创建哈希表
            HashTable hashTable = new HashTable(7);
    
            //写一个简单的菜单
            String key = "";
            Scanner scanner = new Scanner(System.in);
            while(true) {
                System.out.println("雇员管理系统:");
                System.out.println("add : 添加雇员    find: 查找雇员");
                System.out.println("list: 显示雇员    del : 删除雇员");
                System.out.println("update:跟新员工   exit: 退出系统");
    
                key = scanner.next();
                switch (key) {
                    case "add":
                        System.out.print("输入id:");
                        int id = scanner.nextInt();
                        System.out.print("输入名字:");
                        String name = scanner.next();
                        //创建雇员
                        Emp emp = new Emp(id, name);
                        hashTable.add(emp);
                        break;
                    case "list":
                        hashTable.list();
                        break;
                    case "find":
                        System.out.print("请输入需要查找的id:");
                        id = scanner.nextInt();
                        hashTable.findEmpId(id);
                        break;
                    case "del":
                        System.out.print("请输入雇员的id:");
                        id = scanner.nextInt();
                        hashTable.delEmpId(id);
                        break;
                    case "update":
                        System.out.print("输入id:");
                        id = scanner.nextInt();
                        System.out.print("输入名字:");
                        name = scanner.next();
                        //创建雇员
                        emp = new Emp(id, name);
                        hashTable.updateEmp(emp);
                        break;
                    case "exit":
                        scanner.close();
                        System.exit(0);
                    default:
                        break;
                }
            }
        }
    }
    
    • 代码汇总
    package h_HashTable;
    
    import java.util.LinkedList;
    import java.util.Scanner;
    
    public class HashTableDemo {
        public static void main(String[] args) {
            //创建哈希表
            HashTable hashTable = new HashTable(7);
    
            //写一个简单的菜单
            String key = "";
            Scanner scanner = new Scanner(System.in);
            while(true) {
                System.out.println("雇员管理系统:");
                System.out.println("add : 添加雇员    find: 查找雇员");
                System.out.println("list: 显示雇员    del : 删除雇员");
                System.out.println("update:跟新员工   exit: 退出系统");
    
                key = scanner.next();
                switch (key) {
                    case "add":
                        System.out.print("输入id:");
                        int id = scanner.nextInt();
                        System.out.print("输入名字:");
                        String name = scanner.next();
                        //创建雇员
                        Emp emp = new Emp(id, name);
                        hashTable.add(emp);
                        break;
                    case "list":
                        hashTable.list();
                        break;
                    case "find":
                        System.out.print("请输入需要查找的id:");
                        id = scanner.nextInt();
                        hashTable.findEmpId(id);
                        break;
                    case "del":
                        System.out.print("请输入雇员的id:");
                        id = scanner.nextInt();
                        hashTable.delEmpId(id);
                        break;
                    case "update":
                        System.out.print("输入id:");
                        id = scanner.nextInt();
                        System.out.print("输入名字:");
                        name = scanner.next();
                        //创建雇员
                        emp = new Emp(id, name);
                        hashTable.updateEmp(emp);
                        break;
                    case "exit":
                        scanner.close();
                        System.exit(0);
                    default:
                        break;
                }
            }
        }
    }
    
    //员工  代表链表上的节点
    class Emp {
        public int id;
        public String name;
        public Emp next; //next 默认为null
    
        public Emp(){}
        public Emp(int id, String name) {
            this.id = id;
            this.name = name;
        }
    
        @Override
        public String toString() {
            return "Emp{" +
                    "id=" + id +
                    ", name='" + name + '\'' +
                    '}';
        }
    }
    
    //创建HashTable 管理多条链表
    class HashTable{
        private EmpLinkedList[] LinkedList;
        private int size ;//表示共有多少条链表
    
        public HashTable(int size){
            this.size = size;
            //初始化LinkedList
            LinkedList = new EmpLinkedList[size];
            //还未初始化 null , 分别为每个链表初始化
            for (int i = 0; i < size; i++) {
                LinkedList[i] = new EmpLinkedList();
            }
        }
    
        //添加雇员
        public void add(Emp emp){
            //根据员工id,找到员工应该在哪条链表下
            int LinkedListIndex = hashFun(emp.id);
            //将emp 添加到对应的链表中
    //        LinkedList[LinkedListIndex].addEmp(emp);
    		//按id大小进行排序
            LinkedList[LinkedListIndex].addEmpById(emp);
        }
    
        //遍历哈希表
        public void list(){
            for (int i = 0; i < size; i++) {
                LinkedList[i].list(i);
            }
        }
    
        public void findEmpId(int id){
            //得到该员工id在hashtable上那个角标
            int index = hashFun(id);
            //进入该链表查找员工
            Emp emp = LinkedList[index].findEmp(id);
            if(emp == null){
                System.out.println("未找到");;//表示遍历完,还未找到该节点 返回null
            }else{
                System.out.println(emp.toString());
            }
        }
        public void delEmpId(int id){
            //得到该员工id在hashtable上那个角标
            int index = hashFun(id);
            //进入该链表查找员工
            LinkedList[index].delete(id);
        }
    
        public void updateEmp(Emp emp){
            int index = hashFun(emp.id);
            //进入该链表查找员工
            LinkedList[index].update(emp);
        }
        //编写一个散列函数,使用取模法
        public int hashFun(int id){
            return id % size;
        }
    }
    
    //创建EmpLinkedList 表示链表
    class EmpLinkedList{
        //头指针,执行第一个Emp,因那次我们这个链表的head直接指向第一个Emp
        public Emp head; //默认为null
    
        //添加员工到链表
        public void addEmp(Emp emp){
            if(head == null){
                head = emp;
                return;
            }
            //不能添加已有id员工
            Emp findEmp = findEmp(emp.id);
            if(findEmp != null){
                System.out.println("已存在id= "+findEmp.toString()+"的员工,不能添加重复id员工"+emp.toString());
                return;
            }
            //不是第一个员工,定义一个辅助指针
            Emp curTemp = head;
            while(curTemp.next != null){
                curTemp = curTemp.next;//后移
            }
            //退出时将emp加入链表
            curTemp.next = emp;
    
        }
    
        //按id从小到大 添加员工到链表
        public void addEmpById(Emp emp){
            if(head == null){
                head = emp;
                return;
            }
            //不能添加已有id员工
            Emp findEmp = findEmp(emp.id);
            if(findEmp != null){
                System.out.println("已存在id= "+findEmp.toString()+"的员工,不能添加重复id员工"+emp.toString());
                return;
            }
            //如果新加结点比头节点小
            if(head.id > emp.id){
                Emp temp = null;
                emp.next = head;
                temp = head;
                head = emp;
                return;
            }
            
            //定义一个辅助指针
            Emp curTemp = head;
            while( true){
                //遍历到末尾还未找到,添加
                if(curTemp.next == null &&curTemp.id < emp.id){
                    curTemp.next = emp;
                    break;
                }
               
                if(curTemp.next.id > emp.id){
                    emp.next = curTemp.next;
                    curTemp.next = emp;
                    break;
                }
                curTemp = curTemp.next;
    
            }
    
        }
    
        //遍历链表
        public void list(int index){
            if(head == null){
                System.out.println("第"+(index+1)+"链表为空。");
                return;
            }
    
            Emp curTemp = head; //辅助指针
            System.out.println("第"+(index+1)+"链表信息如下:");
            while(curTemp != null){
                System.out.println(curTemp.toString());
                curTemp = curTemp.next;
            }
        }
    
        //从链表删除员工
        //链表删除需要找到删除结点的前一个节点,因此分为第一个节点和第2-n结点判断
        public void delete( int id){
            if(head == null){
                System.out.println("当前链表为空。");
                return;
            }
            //头节点直接删除
            if(head.id == id){
                head = head.next;
                System.out.println("Id为" + id + "的员工已经被删除~~");
                return;
            }
            Emp curTemp = head; //辅助指针
            while (true){
                if(curTemp.next == null ){
                    break;
                }
    
                if( curTemp.next.id == id){
                    curTemp.next = curTemp.next.next;
                    System.out.println("Id为" + id + "的员工已经被删除~~");
                    return;//删除之后直接退出,否则还会向下执行
                }
    
                curTemp =curTemp.next;
    
            }
        }
    
        //修改员工信息
        public void update( Emp emp){
            if(head == null){
                System.out.println("当前链表为空。");
                return;
            }
            Emp findEmp = findEmp(emp.id);
            if(findEmp == null){
                System.out.println("未找到id = "+emp.id+"员工信息");
                return;
            }
            Emp curTemp = head; //辅助指针
            while (true){
              
                if(curTemp == null ){
                    break;
                }
                if( curTemp.id == emp.id){
                    curTemp.name = emp.name;
                    return;//跟新之后直接退出,否则还会向下执行
                }
                curTemp =curTemp.next;
    
    
            }
        }
    
        //查找员工
        public Emp findEmp( int id){
            if(head == null){
                System.out.println("当前链表为空。");
                return null;
            }
            Emp curTemp = head; //辅助指针
           
    
            while (curTemp != null){
                if( curTemp.id == id){
                    //System.out.println(curTemp.toString());
                    return curTemp;
                }
                curTemp =curTemp.next;
            }
    
            return null;
        }
        //根据id查询雇员
        //如果查找到,就返回Emp,没有找到,就返回null
        public Emp findEmpId(int id){
            //判断链表是否为空
            if(head == null){
                System.out.println("链表为空.");
                return null;
            }
            //辅助指针
            Emp curEmp = head;
            while(true){
                if(curEmp.id == id){	//找到
                    break;	//此时curEmp就指向要查找的雇员
                }
                //退出
                if(curEmp.next == null){	//未找到该雇员
                    curEmp = null;
                    break;
                }
                curEmp = curEmp.next;	//后移
            }
            return curEmp;
        }
    }
    
    展开全文
  • 8.0 哈希表

    2020-08-10 23:16:55
    哈希表的基本介绍: 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个中映射函数叫做散列...

    哈希表的基本介绍:
    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个中映射函数叫做散列函数,存放记录的数组叫做散列表。
    在这里插入图片描述哈希表的实例运用:
    google公司的一个上机题:
    有一个公司,当有新的员工来报道时要求将该员工的信息加入(id,性别年龄,名字,住址…),当输入该员工的id时,要求查找到该员工所有信息.
    要求:
    不使用数据库,速度越快越好=>哈希表(散列)添加时,保证按照id从低到高插入[课后思考:如果id不是从低到高插入,但要求各条链表仍是从低到高,怎么解决?]
    1)使用链表来实现哈希表,该链表不带表头[即:链表的第一-个结点就存放雇员信息]
    2)思路分析并画出示意图
    3)代码实现[增删改查(显示所有员工,按id查询)]

    思路分析图:
    在这里插入图片描述代码实现:

    package HashTable;
    import java.util.Scanner;
    
    public class HashTableDemo {
        public static void main(String[] args) {
            //创建哈希表
            HashTab hashTab = new HashTab(7);
    
            //写一个菜单
            String key = "";
            Scanner scanner = new Scanner(System.in);
            while (true){
                System.out.println("add: 添加");
                System.out.println("delete: 删除");
                System.out.println("list: 显示");
                System.out.println("find: 查找");
                System.out.println("exit: 退出");
                key = scanner.next();
                switch (key){
                    case "delete":
                        System.out.println("输入要删除的id");
                        int id = scanner.nextInt();
                        hashTab.delete(id);
                        break;
                    case "add":
                        System.out.println("输入id");
                        id = scanner.nextInt();
                        System.out.println("输入名字");
                        String name = scanner.next();
                        Emp emp = new Emp(id, name);
                        hashTab.addByOrder(emp);
                        break;
                    case "list":
                        hashTab.list();
                        break;
                    case "find":
                        id = scanner.nextInt();
                        hashTab.findEmpById(id);
                        break;
                    case "exit":
                        scanner.close();
                        System.exit(0);
                    default:
                        break;
                }
            }
        }
    }
    
    //创建HashTab管理多条链表
    class HashTab{
        private EmpLinkedList[] empLinkedListArray;
        private int size;
    
        //构造器
        public HashTab(int size) {
           this.size = size;
           //初始化empLinkedListArray
            empLinkedListArray = new EmpLinkedList[size];
            //每一个链表都需要初始化
            for (int i = 0; i < size; i++) {
                empLinkedListArray[i] = new EmpLinkedList();
            }
        }
    
        //添加雇员
        public void add(Emp emp){
            //根据id,得到该节点应该添加到那一条链表
            int empLinkedListNo = hashFun(emp.id);
            //将emp添加到对应的链表中
            empLinkedListArray[empLinkedListNo].add(emp);
        }
    
        //添加节点不重复顺序
        public void addByOrder(Emp emp){
            int empLinkedListNo = hashFun(emp.id);
            empLinkedListArray[empLinkedListNo].add1(emp);
        }
    
        //删除节点
        public void delete(int id){
            int empLinkedListNo = hashFun(id);
            empLinkedListArray[empLinkedListNo].delete(id);
    
        }
    
        //遍历所有的链表
        public void list(){
            for (int i = 0; i < size; i++){
                empLinkedListArray[i].list(i);
            }
        }
    
        //根据id查找节点
        public void findEmpById(int id){
            int empLinkedListNo = hashFun(id);
            Emp emp = empLinkedListArray[empLinkedListNo].findEmpById(id);
            if (emp != null){
                System.out.printf("在第"+empLinkedListNo+"找到该节点  节点id = %d\n",id);
            }else {
                System.out.println("没有该节点");
            }
        }
    
        //编写散列函数,使用一个简单的去模法
        public int hashFun(int id){
            return id % size;
        }
    
    }
    
    //表示一个雇员
    class Emp{
        public int id;
        public String name;
        public Emp next;
    
        public Emp(int id, String name) {
            this.id = id;
            this.name = name;
        }
    }
    
    class EmpLinkedList{
        //头指针,默认为空
        private Emp head;
    
        //添加雇员到链表
        public void add(Emp emp){
            if (head == null){
                head = emp;
                return;
            }
            //如果不是第一个节点,则需要使用一个辅助指针
            Emp curEmp = head;
            while (true){
                if (curEmp.next == null){
                    break;
                }
                curEmp = curEmp.next;
            }
            curEmp.next = emp;
        }
    
        //按顺序添加
        public void add1(Emp emp){
            if (head == null){
                head = emp;
                return;
            }
            Emp curEmp = head;
            if (emp.id < head.id){
                emp.next = head;
                head = emp;
            }else if (emp.id == curEmp.id){
                System.out.println("请勿重复添加");
            }else {
                while (true){
                    if (curEmp.next == null){
                        break;
                    }else if (curEmp.next.id > emp.id){
                       break;
                    }
                    curEmp = curEmp.next;
                }
                emp.next = curEmp.next;
                curEmp.next = emp;
            }
        }
    
        //删除相应id节点
        public void delete(int id){
            if (head == null){
                System.out.println("删除失败,该链表为空");
                return;
            }
            if (head.id == id){
                head = head.next;
                System.out.println("删除成功");
            }else {
                boolean flag;
                Emp prev = head;
                while (true){
                    if (prev.next == null){
                        flag = false;
                        break;
                    }else if (prev.next.id == id){
                        flag = true;
                        break;
                    }
                    prev = prev.next;
                }
                if (flag){
                    prev.next = prev.next.next;
                    System.out.println("删除成功");
                }else {
                    System.out.println("没有该节点删除失败");
                }
            }
    
        }
    
        //遍历链表
        public void list(int no){
            if (head == null){
                System.out.println("第"+ no +"链表信息为:");
                return;
            }
            System.out.print("第"+ no +"链表信息为:");
            Emp curEmp = head;
            while (true){
                System.out.printf("=> id = %d name = %s\t", curEmp.id,curEmp.name);
                if (curEmp.next == null){
                    break;
                }
                curEmp = curEmp.next;
            }
            System.out.println();
        }
    
        //根据id查找雇员
        public Emp findEmpById(int id){
            if (head == null){
                System.out.println("链表为空");
                return null;
            }
            //辅助指针
            Emp curEmp = head;
            while (true){
                if (curEmp.id == id){
                    break;
                }
                if (curEmp.next == null){
                    curEmp = null;
                    break;
                }
                curEmp = curEmp.next;
            }
            return curEmp;
        }
    }
    
    展开全文
  • 哈希码冲突解法示意图 底层实现:ArrayList<Object>[]链表数组 先用hashcode找到元素所在链表位置, 再遍历链表通过equals()比较对应元素,避免冲突。 java各种比较方式: hashCode()...
  • 简单哈希表实现

    2018-05-24 15:48:30
    哈希表定义:  哈希表又称散列表,是根据关键码值(key value)而直接访问的数据结构。它通过把关键码值映射到表中一个位置来...哈希表结构示意图:   下面编写一个简单实例: 1.头的定义: typedef struct...
  • 哈希表的简单实现

    2021-01-27 09:25:25
    哈希表的基本介绍 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数...
  • 哈希表(数组+链表实现)

    千次阅读 2020-02-23 11:32:16
    1.1 哈希表(散列)实际需求- 某公司上机题 有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址…),当输入该员工的id 时,要求查找到该员工的 所有信息. 要求: 不使用数据库,尽量节省内存,...
  • 数据结构-哈希表

    2021-05-08 09:46:11
    哈希表 1、哈希表的基本介绍 2、google公司的一个上机题
  • 哈希表笔记

    2020-10-06 15:39:01
    哈希表(HashTable) 基本介绍 散列表(Hash table, 也叫哈希表), 是根据关键码值(Key value)而直接进行访问的数据结构。 也就是说, 它通过把关键码值映射到表中一个位置来访问记录, 以加快查找的速度。这个...
  • Java-哈希表

    2020-10-17 20:40:54
    哈希表的基本介绍 散列表(Hash table,也叫哈希表),是根据关键码值(key value)而直接进行访问的数据结构,也就是说,它通过把关键码值映射到表中一个位置来访问记录,...示意图 代码实现 //表示一个雇员 class E
  • 哈希表 哈希表又称散列表,是根据关键字key来加速访问...示意图 代码示例 HashTab 用户直接操作的哈希表 NodeLinkedList 哈希表中数组中内部维护的一个链表 Node 存储数据的节点 真正保存数据的类 HashTab中的增删改
  • 详谈哈希表

    2020-08-18 21:39:28
    根据设定的哈希函数H(key)H(key)H(key) 和处理冲突的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表便称为 哈希表,这一映像过程称为哈希...
  • 哈希表&布隆过滤器

    2020-08-15 15:29:45
    哈希表 使用哈希表可以进行非常快速的查找操作,查找时间为常数,同时不需要元素排列有序 python的内建数据类型:字典,就是用哈希表实现的 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接...
  • 哈希表及其企业级应用

    多人点赞 2021-04-18 16:09:57
    这里写目录标题哈希表的原理精讲哈希表结构体定义企业级应用文件接口储存基本单位文件存储单位文件结构 哈希表的原理精讲 哈希表 - 散列表,它是基于快速存取的角度设计的,也是一种典型...原理示意图: 哈希表结构体定
  • 哈希表是一种存储键值对(key-value)的数据结构,根据键查找值的时间复杂度为O(1)。我们经常见到的哈希表都是采用数组+链表实现(即所谓的拉链法)。 与普通哈希表不同,nginx哈希表有以下特点: 创建nginx哈希表...
  • PHP哈希表碰撞攻击原理

    千次阅读 2016-01-05 13:02:56
    最近哈希表碰撞攻击(Hashtable collisions as DOS attack)的话题不断被提起,各种语言纷纷中招。本文结合PHP内核源码,聊一聊这种攻击的原理及实现。 哈希表碰撞攻击的基本原理 哈希表是一种查找效率极高的...
  • 哈希表(Hash table)

    2020-07-03 07:40:10
    哈希表(Hash table) 1.哈希表的基本介绍 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。...
  • 查找算法与哈希表

    2020-11-11 00:37:48
    哈希表思维导图5.1 哈希表基本介绍5.2 哈希表的实现5.3 代码实现 思维导图 1.线性查找 线性查找也叫顺序查找,这是最基本的一种查找方法,从给定的值中进行搜索,从一端开始逐一检查每个元素,直到找到所需元素的...
  • 哈希函数(哈希表) 1.概念 2.用法注意点 四.运用哈希表来编写实现一个<学生信息管理系统> 笔记: 一.排序 1.插入排序: 先构建一个有序的序列,遍历无序的序列,将无序的序列中的每一个元素和有序序列中的...
  • 哈希表和简单用法

    2021-06-21 01:13:30
    哈希表 哈希表的基本介绍 散列表(Hash table ,也叫哈希表),是根据关键码值(Key Value)而直接进行访问的数据结构,也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度,这个映射函数就叫做...
  • Java编程:哈希表

    2020-09-30 17:04:07
    Java编程:哈希表

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,873
精华内容 3,949
关键字:

哈希表的示意图