哈希表

1. 基本介绍

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

2. 实现

• 哈希表可看作数组与链表的结合，将所有节点，以某种散列方式分布到特定数组下标对应的链表上。
• 查询、删除、添加、修改，都需要hash散列找到对应的下标，然后通过链表节点遍历的方式进行查找
• 优势：
  • 相比于纯单链表，一定程度减少了添加节点的速度以及查询节点的速度，因为有数组，通过散列就能快速定位到特定链表
  • 相比于纯数组，添加元素不会上限，不需要进行扩容
• 缺点：
  • 相比于链表，需要一段连续的存储空间（存放链表头节点的数组）
  • 相比于数组，查询或者修改某个元素的数据时间稍微慢一些，因为索引到对应链表后，还是需要进行遍历链表查找对应的节点 ```java /**
    • 1. 构造器
    • 1. hash散列
    • 1. 添加
    • 1. 根据id查询
    • 1. 遍历所有 */ public class HashTable { private LinkedList[] linkedLists; private int size; // 1. 构造器 public HashTable(int size){ this.size = size; linkedLists = new LinkedList[this.size]; // 将链表数组中的每个链表元素进行初始化(创建一个地址空间) for (int i=0;i<size;i++){ linkedLists[i] = new LinkedList(); } } // 2. hash散列 public int hash(int id){ return id%size; } // 3. 添加 public void add(DataNode node){ int no = hash(node.id); linkedLists[no].add(node); } // 4. 根据id查询 public DataNode findById(int id){ int no = hash(id); return linkedLists[no].getById(id); } // 5. 遍历所有 public void list(){ for (int i=0;i<size;i++){ linkedLists[i].list(); } } }

/**

• 需要的方法:
• 1. 添加节点
• 1. 遍历链表
• 1. 根据id查找链表 */ public class LinkedList { public DataNode head; // 1. 添加节点 public void add(DataNode node){ if (head==null){ head = node; return; } // 头节点不为空, 那么指定 DataNode temp = head; // 设置辅助指针 while(temp.next!=null){ // 找到需要添加的地方 temp = temp.next; } temp.next = node; } // 2. 遍历链表 public void list(){ if (head==null){ System.out.println(“链表为空,无法遍历!”); return; } DataNode temp = head; while(temp!=null){ System.out.println(temp); temp = temp.next; } System.out.println(); } // 3. 根据id查找链表 public DataNode getById(int id){ if (head==null){ System.out.println(“链表为空!”); return null; } DataNode temp = head; while(temp!=null){ if (temp.id==id){

      return temp;

     } temp = temp.next; } return null; } }

public class DataNode { public int id; public String name; public DataNode next;

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

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

} ```