模拟hashMap即hash表

2022/4/18 23:12:34

本文主要是介绍模拟hashMap即hash表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1.背景

hashMy经常使用,那么底层是怎么样实现的了,今天我们模拟写一个..

2.代码实现

package com.ldp.structure.demo05HashTable;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @create 04/18 8:47
 * @description <p>
 * 自动以hashTable表,即模拟一个HashMapper
 * </p>
 */
public class Test01 {
    /**
     * 基于数组的栈演示
     *
     * @param args
     */
    public static void main(String[] args) {
        MyHashTable myHashTable = new MyHashTable(16);
        Scanner scanner = new Scanner(System.in);
        String key = "";
        boolean flag = true;
        while (flag) {
            System.out.println("(l)list查看队列");
            System.out.println("(a)add添加一个元素");
            System.out.println("(g)g获取一个元素");
            System.out.println("(e)exit退出系统");
            key = scanner.next();
            switch (key) {
                case "l":
                    myHashTable.list();
                    break;
                case "a":
                    System.out.println("请输入id:");
                    String id = scanner.next();
                    System.out.println("请输入数据:");
                    String data = scanner.next();
                    myHashTable.add(new MyNode(id, data));
                    break;
                case "g":
                    try {
                        System.out.println("请输入id:");
                        MyNode myNode = myHashTable.getById(scanner.next());
                        System.out.println("查询到的数据是:" + myNode);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "e":
                    System.out.println("退出系统");
                    flag = false;
                    break;
                default:
                    System.out.println("输入错误");
            }
        }
    }
}

/**
 * 自定义的hash表
 */
class MyHashTable {
    private MyLinkedList[] array;
    private Integer size;

    public MyHashTable(Integer size) {
        this.size = size;
        this.array = new MyLinkedList[size];
        // 初始化链表对象
        for (int i = 0; i < size; i++) {
            array[i] = new MyLinkedList();
        }
    }

    /**
     * 添加
     *
     * @param myNode
     */
    public void add(MyNode myNode) {
        Integer index = getIndex(myNode.getId());
        array[index].add(myNode);
    }

    /**
     * 遍历链表中的数据
     */
    public void list() {
        for (int i = 0; i < size; i++) {
            array[i].list(i);
            System.out.println();
        }
    }

    /**
     * 根据id获取数据
     *
     * @param id
     * @return
     */
    public MyNode getById(String id) {
        Integer index = getIndex(id);
        MyNode myNode = array[index].getById(id);
        return myNode;
    }

    /**
     * 散列算法,获取到一个存入的下标
     *
     * @param id
     * @return
     */
    public Integer getIndex(String id) {
        char[] chars = id.toCharArray();
        System.out.println("==>" + Arrays.toString(chars));
        int sum = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] >= 'A' && chars[i] <= 'Z') {
                sum = sum * 52 + (chars[i] - 'A');
            } else {
                sum = sum * 52 + (chars[i] - 'a') + 26;
            }
        }
        System.out.println("sum=" + sum);
        return Math.abs(sum) % size;
    }
}

/**
 * 链表
 */
class MyLinkedList {
    private MyNode head;

    public MyLinkedList() {
    }

    public MyLinkedList(MyNode head) {
        this.head = head;
    }

    /**
     * 添加一个节点
     *
     * @param myNode
     */
    public void add(MyNode myNode) {
        // 如果还没有头结点
        if (this.head == null) {
            this.head = myNode;
            return;
        }
        // 根据头结点一次找下一个节点
        MyNode temp = head;
        while (true) {
            if (temp.getNext() == null) {
                temp.setNext(myNode);
                break;
            } else {
                temp = temp.getNext();
            }
        }
    }

    /**
     * 遍历节点
     */
    public void list(int index) {
        MyNode temp = this.head;
        if (temp == null) {
            System.out.println("第:" + (index + 1) + " 条链表无数据....");
            return;
        }
        while (temp != null) {
            System.out.println("第:" + (index + 1) + " 条链表:" + temp);
            temp = temp.getNext();
        }
    }

    /**
     * 根据id查找
     *
     * @param id
     */
    public MyNode getById(String id) {
        if (this.head == null) {
            System.out.println("不存在id=" + id + "的数据");
            return null;
        }
        MyNode temp = this.head;
        while (temp != null) {
            if (id.equals(temp.getId())) {
                return temp;
            } else {
                temp = temp.getNext();
            }
        }
        System.out.println("链表有数据但,不存在id=" + id + "的数据");
        return null;
    }

    public MyNode getHead() {
        return head;
    }

    public void setHead(MyNode head) {
        this.head = head;
    }
}

/**
 * 节点
 */
class MyNode {
    private String id;
    private Object data;
    private MyNode next;

    public MyNode(String id, Object data) {
        this.id = id;
        this.data = data;
    }

    public String getId() {
        return id;
    }

    public void setId(String id) {
        this.id = id;
    }

    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        this.data = data;
    }

    public MyNode getNext() {
        return next;
    }

    public void setNext(MyNode next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "MyNode{" +
                "id='" + id + '\'' +
                ", data=" + data +
                '}';
    }
}

 

完美!



这篇关于模拟hashMap即hash表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程