散列表
散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
散列函数
散列函数，顾名思义，它是一个函数。如果把它定义成 hash(key) ，其中 key 表示元素的键值，则 hash(key) 的值表示经过散列函数计算得到的散列值。
散列函数的特点：
1.确定性
如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。
2.散列碰撞（collision）
散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同。
3.不可逆性
一个哈希值对应无数个明文，理论上你并不知道哪个是。
“船长，如果一样东西你知道在哪里，还算不算丢了。”
“不算。”
“好的，那您的酒壶没有丢。”
4.混淆特性
输入一些数据计算出散列值，然后部分改变输入值，一个具有强混淆特性的散列函数会产生一个完全不同的散列值。
常见的散列函数
这里，需要了解的是，构造散列函数应遵循的 原则 是：
散列值（value）是一个非负数：常见的学号、内存寻址呀，都要求散列值不可能是负数 key 值相同，通过散列函数计算出来的散列值（value）一定相同 key 值不同，通过散列函数计算出来的散列值（value）不一定不相同
看一个例子：学校最近要盖一个图书馆，用于学生自习，如果给每位学生提供单独的小桌子的话，就需要 10w 张，这显然是不可能的，那么，有没有办法在得到 O(1) 的查找效率的同时、又不付出太大的空间代价呢？
散列函数就提供了这种解决方案，10w 是多，但如果我们除以 100 喃，那就 0～999，这就好找了，也不用那么多桌子了。
1. MD5
MD5 即 Message-Digest Algorithm 5（信息-摘要算法5），用于确保信息传输完整一致。是计算机广泛使用的杂凑算法之一，主流编程语言普遍已有 MD5 实现。
将数据（如汉字）运算为另一固定长度值，是杂凑算法的基础原理，MD5 的前身有 MD2 、MD3 和 MD4 。
MD5 是输入不定长度信息，输出固定长度 128-bits 的算法。经过程序流程，生成四个32位数据，最后联合起来成为一个 128-bits 散列。
基本方式为，求余、取余、调整长度、与链接变量进行循环运算，得出结果。
MD5 计算广泛应用于错误检查。在一些 BitTorrent 下载中，软件通过计算 MD5 来检验下载到的碎片的完整性。
2. SHA-1
SHA-1（英语：Secure Hash Algorithm 1，中文名：安全散列算法1）是一种密码散列函数，SHA-1可以生成一个被称为消息摘要的160位（20字节）散列值，散列值通常的呈现形式为40个十六进制数。
SHA-1 曾经在许多安全协议中广为使用，包括TLS和SSL、PGP、SSH、S/MIME和IPsec，曾被视为是MD5的后继者。
3. 其他常用的散列函数
点击查看
4. 一个好的散列函数需要具有以下基本要求
易于计算：它应该易于计算，并且不能成为算法本身。 统一分布：它应该在哈希表中提供统一分布，不应导致群集。 较少的冲突：当元素对映射到相同的哈希值时发生冲突。应该避免这些。
散列冲突
理想中的一个散列函数，希望达到
如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)
这种效果，然而在真实的情况下，要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不可能的，即使是 MD5 或者 由美国国家安全局设计的 SHA-1 算法也无法实现。
事实上，再好的散列函数都无法避免散列冲突。
为什么呢？
这涉及到数学中比较好理解的一个原理：抽屉原理。
抽屉原理：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面至少放两个苹果。这一现象就是我们所说的“抽屉原理”。
对于散列表而言，无论设置的存储区域（n）有多大，当需要存储的数据大于 n 时，那么必然会存在哈希值相同的情况。这就是所谓的散列冲突。
那应该如何解决散列冲突问题呢？
解决冲突方法主要由以下几种
开放地址法（也叫开放寻址法）：实际上就是当需要存储值时，对Key哈希之后，发现这个地址已经有值了，这时该怎么办？不能放在这个地址，不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希，比如往后移动一个地址，如果没人占用，就用这个地址。如果超过最大长度，则可以对总长度取余。这里移动的地址是产生冲突时的增列序量。 链地址法：链地址法其实就是对Key通过哈希之后落在同一个地址上的值，做一个链表。其实在很多高级语言的实现当中，也是使用这种方式处理冲突的，我们会在后面着重学习这种方式。 再哈希法：在产生冲突之后，使用关键字的其他部分继续计算地址，如果还是有冲突，则继续使用其他部分再计算地址。这种方式的缺点是时间增加了。 建立一个公共溢出区：这种方式是建立一个公共溢出区，当地址存在冲突时，把新的地址放在公共溢出区里。
常用的散列冲突解决方法有两类，开放寻址法（open addressing）和链地址法（chaining）。
开放寻址法
定义：将散列函数扩展定义成探查序列，即每个关键字有一个探查序列h(k,0)、h(k,1)、…、h(k,m-1)，这个探查序列一定是0….m-1的一个排列（一定要包含散列表全部的下标，不然可能会发生虽然散列表没满，但是元素不能插入的情况），如果给定一个关键字k，首先会看h(k,0)是否为空，如果为空，则插入；如果不为空，则看h(k,1)是否为空，以此类推。
开放寻址法是一种解决碰撞的方法，对于开放寻址冲突解决方法，比较经典的有线性探测方法（Linear Probing）、二次探测（Quadratic probing）和 双重散列（Double hashing）等方法。
线性探测方法
当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。
以上图为例，散列表的大小为 8 ，黄色区域表示空闲位置，橙色区域表示已经存储了数据。目前散列表中已经存储了 4 个元素。此时元素 7777777 经过 Hash 算法之后，被散列到位置下标为 7 的位置，但是这个位置已经有数据了，所以就产生了冲突。
于是按顺序地往后一个一个找，看有没有空闲的位置，此时，运气很好正巧在下一个位置就有空闲位置，将其插入，完成了数据存储。
线性探测法一个很大的弊端就是当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下，需要从头到尾探测整个散列表，所以最坏情况下的时间复杂度为 O(n)。
二次探测方法
二次探测是二次方探测法的简称。顾名思义，使用二次探测进行探测的步长变成了原来的“二次方”，也就是说，它探测的下标序列为 hash(key)+0，hash(key)+1^2或[hash(key)-1^2]，hash(key)+2^2或[hash(key)-2^2]。
以上图为例，散列表的大小为 8 ，黄色区域表示空闲位置，橙色区域表示已经存储了数据。目前散列表中已经存储了 7 个元素。此时元素 7777777 经过 Hash 算法之后，被散列到位置下标为 7 的位置，但是这个位置已经有数据了，所以就产生了冲突。
按照二次探测方法的操作，有冲突就先 + 1^2，8 这个位置有值，冲突；变为 - 1^2，6 这个位置有值，还是有冲突；于是 - 2^2， 3 这个位置是空闲的，插入。
双重散列方法
所谓双重散列也就是再哈希法，意思就是不仅要使用一个散列函数，而是使用一组散列函数 hash1(key)，hash2(key)，hash3(key)。。。。。。先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。这个再哈希函数应该满足两个条件，一： 和原哈希函数应该不同，二 得到的结果值不能是0. 因为步长是0，就会原地踏步，陷入死循环。
还有一个注意点，再哈希探测要求数组长度是质数，为什么有这个奇怪要求呢？主要是防止一种情况，得到的步长是数组长度的因子。例如 数组长度是10，哈希化得到下标值是0或者5，得到的步长正好也是5.
这个时候就有问题了，你会发现我们的探测序列一直是 0、5、10、0、5等等，是一个死循环，没办法找其他位置。但是如果数组长度是个质数，那么它的探测序列就不一样咯，0、5、10、4、9、3、8、2、7、1、6、0 你会发现会它会遍历数组所有位置。
以上图为例，散列表的大小为 8 ，黄色区域表示空闲位置，橙色区域表示已经存储了数据。目前散列表中已经存储了 7 个元素。此时元素 7777777 经过 Hash 算法之后，被散列到位置下标为 7 的位置，但是这个位置已经有数据了，所以就产生了冲突。
此时，再将数据进行一次哈希算法处理，经过另外的 Hash 算法之后，被散列到位置下标为 3 的位置，完成操作。
测试代码如下
class DataItem {
private String data;
// 用deleteItem这个静态变量标记已删除元素。因为在链表删除的时候，是不能将数组中的元素置位null，用这个标记
public static final DataItem deleteItem = new DataItem();
public DataItem() {
}
public DataItem(String data) {
this.data = data;
}
public String getData() {
return data;
}
@Override
public boolean equals(Object obj) {
if (!(obj instanceof DataItem)) return false;
DataItem other = (DataItem) obj;
return this.data == other.data;
}
// 用来缓存hash值，避免每次都计算hashCode值
private int hash;
// 注意这里计算hashCode方法，很容易就数值溢出了，即超出int类型的最大值。
@Override
public int hashCode() {
if (hash != 0 ) return hash;
char[] chars = data.toCharArray();
int h = 0;
for (int i = 0; i < chars.length; i++) {
char ch = chars[i];
h = h * 31 + ch;
}
hash = h;
return h;
}
@Override
public String toString() {
final StringBuilder sb = new StringBuilder(" {");
sb.append("data=").append(data);
sb.append('}');
return sb.toString();
}
}
public class DoubleHash {
private DataItem[] store;
private int maxSize;
private int size;
public DoubleHash(int maxSize) {
this.maxSize = maxSize;
store = new DataItem[maxSize];
size = 0;
}
// 哈希化 函数
private int hashFunc(int hashCode) {
return hashCode % maxSize;
}
// 再哈希，得到步长
private int getFuncStep(int hashCode) {
return 5 - hashCode % 5;
}
public void insert(DataItem value){
int hashCode = value.hashCode();
// 得到哈希化之后的值
int hashIndex = hashFunc(hashCode);
// 通过哈希值，得到步长step
int step = getFuncStep(hashCode);
// hashIndex对应坐标的不为null，且没有被删除，那么就查找下一个元素。
// 直到找到hashIndex对应位置 元素 为空，或者被删除。那么就在这个位置插入新元素。
// 注意这里没有考虑 死循环的情况
while (store[hashIndex] != null && store[hashIndex] != DataItem.deleteItem) {
hashIndex = hashIndex + step;
// 不能使用hashIndex == maxSize这个条件了，因为hashIndex不再是每次自增1，那么就有可能跳过maxSize这个值。
hashIndex = hashIndex % maxSize;
}
store[hashIndex] = value;
size++;
}
public DataItem get(int hashCode) {
// 得到哈希化之后的值
int hashIndex = hashFunc(hashCode);
// 通过哈希值，得到步长step
int step = getFuncStep(hashCode);
// 跳出循环的条件有两个，一个是找到一个空白元素，表示没有查到对应元素，二是找到相同hashCode的值，返回它。
// 注意不能将被删除元素作为循环终止条件,被删除元素只能作为继续查找下一个元素的条件
while (store[hashIndex] != null) {
// 如果hashIndex对应位置元素被删除了，那么就查找下一个元素。
// 注意这里千万不能将store[hashIndex] != DataItem.deleteItem判断条件放到while循环中。
if (store[hashIndex] != DataItem.deleteItem) {
DataItem temp = store[hashIndex];
if (temp.hashCode() == hashCode) {
return temp;
}
}
hashIndex = hashIndex + step;
hashIndex = hashIndex % maxSize;
}
return null;
}
public DataItem remove(int hashCode) {
int hashIndex = hashFunc(hashCode);
// 通过哈希值，得到步长step
int step = getFuncStep(hashCode);
// 跳出循环的条件有两个，一个是找到一个空白元素，表示没有查到对应元素，
// 二是找到相同hashCode的值，就将hashIndex对应下标元素换成deleteItem，表示已删除
// 注意不能将被删除元素作为循环终止条件,被删除元素只能作为继续查找下一个元素的条件
while (store[hashIndex] != null) {
// 如果hashIndex对应位置元素被删除了，那么就查找下一个元素。
// 注意这里千万不能将store[hashIndex] != DataItem.deleteItem判断条件放到while循环中。
if (store[hashIndex] != DataItem.deleteItem) {
DataItem temp = store[hashIndex];
if (temp.hashCode() == hashCode) {
size --;
store[hashIndex] = DataItem.deleteItem;
return temp;
}
}
hashIndex = hashIndex + step;
hashIndex = hashIndex % maxSize;
}
return null;
}
public int getSize() {
return size;
}
public static void main(String[] args){
DoubleHash lineHash = new DoubleHash(333);
for (int i = 0; i < 100; i++) {
DataItem dataItem = new DataItem(i+"_"+i);
lineHash.insert(dataItem);
}
System.out.println("size === "+ lineHash.getSize());
DataItem keyDataItem1 = new DataItem("50_50");
DataItem keyDataItem2 = new DataItem("25_25");
// 查询方法是否有效
System.out.println("get() ==" +lineHash.get(keyDataItem1.hashCode()));
System.out.println("get() ==" +lineHash.get(keyDataItem2.hashCode()));
// 删除方法是否有效
System.out.println("remove == "+lineHash.remove(keyDataItem1.hashCode()));
// 重复删除不会有异常
System.out.println("remove == "+lineHash.remove(keyDataItem1.hashCode()));
// 删除之后，在哈希表中就查找不到了
System.out.println("get() ==" +lineHash.get(keyDataItem1.hashCode()));
// 删除不会影响其他元素。
System.out.println("get() ==" +lineHash.get(keyDataItem2.hashCode()));
System.out.println("get() ==" +lineHash.get(new DataItem("44_44").hashCode()));
System.out.println("size === "+ lineHash.getSize());
}
}
事实上，不管采用哪种探测方法，只要当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，需要尽可能保证散列表中有一定比例的空闲槽位。
一般使用加载因子（load factor）来表示空位的多少。
加载因子是表示 Hsah 表中元素的填满的程度，若加载因子越大，则填满的元素越多,这样的好处是：空间利用率高了,但冲突的机会加大了。反之,加载因子越小,填满的元素越少,好处是冲突的机会减小了，但空间浪费多了。
链地址法
链地址法是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多。如下动图所示，在散列表中，每个位置对应一条链表，所有散列值相同的元素都放到相同位置对应的链表中。
插入：像对应的链表中插入一条数据，时间复杂度为 O(1)
查找或删除：从链头开始，查找、删除的时间复杂度为 O(k)，k为链表的长度
对应的用例代码如下
class DataItem {
private String data;
// 指向下一个DataItem的引用，形成一个链表
DataItem next;
public DataItem(String data) {
this(data, null);
}
public DataItem(String data, DataItem next) {
this.data = data;
this.next = next;
}
public String getData() {
return data;
}
@Override
public boolean equals(Object obj) {
if (!(obj instanceof DataItem)) return false;
DataItem other = (DataItem) obj;
return this.data == other.data;
}
// 用来缓存hash值，避免每次都计算hashCode值
private int hash;
// 注意这里计算hashCode方法，很容易就数值溢出了，即超出int类型的最大值。
@Override
public int hashCode() {
if (hash != 0 ) return hash;
char[] chars = data.toCharArray();
int h = 0;
for (int i = 0; i < chars.length; i++) {
char ch = chars[i];
h = h * 31 + ch;
}
hash = h;
return h;
}
@Override
public String toString() {
final StringBuilder sb = new StringBuilder(" {");
sb.append("data=").append(data);
sb.append('}');
return sb.toString();
}
}
public class LinkedHash {
private DataItem[] store;
private int maxSize;
private int size;
public LinkedHash(int maxSize) {
this.maxSize = maxSize;
store = new DataItem[maxSize];
size = 0;
}
// 哈希化 函数
private int hashFunc(int hashCode) {
return hashCode % maxSize;
}
public void insert(DataItem value){
size++;
int hashCode = value.hashCode();
// 得到哈希化之后的值
int hashIndex = hashFunc(hashCode);
System.out.println("hashCode=="+hashCode+" hashIndex=="+hashIndex+" value=="+value);
DataItem temp = store[hashIndex];
// 如果对应下标对应元素为空，就将value值存到这个下标位置。value相当于一个链表
if (temp == null) {
store[hashIndex] = value;
return;
}
// 利用循环查找 链表尾，然后将value插入链表尾
while (true) {
if (temp.next == null) break;
temp = temp.next;
}
temp.next = value;
}
public DataItem get(int hashCode) {
// 得到哈希化之后的值
int hashIndex = hashFunc(hashCode);
DataItem temp = store[hashIndex];
// 链表为null，没有这个元素，返回null
if (temp == null) {
return null;
}
// 链表不为空就，遍历链表，查找与hashCode相同的元素，并返回它
while (temp != null) {
if (temp.hashCode() == hashCode) {
return temp;
}
temp = temp.next;
}
// 链表遍历完成之后，还是没有找到，就返回null
return null;
}
public DataItem remove(int hashCode) {
// 得到哈希化之后的值
int hashIndex = hashFunc(hashCode);
DataItem temp = store[hashIndex];
// 链表为null，没有这个元素，返回null，删除失败
if (temp == null) {
return null;
}
DataItem prev = null;
// 链表不为空就，遍历链表，查找与hashCode相同的元素，从列表中删除它。
while (temp != null) {
if (temp.hashCode() == hashCode) {
// 如果prev为空，表示temp是链表头，所以要重新给store[hashIndex]数组赋值
if (prev == null) {
store[hashIndex] = temp.next;
} else {
// prev不为空，就将它的next指向temp的 next，这样就将temp从链表中删除了
prev.next = temp.next;
}
size -- ;
return temp;
}
temp = temp.next;
}
return null;
}
public int getSize() {
return size;
}
public static void main(String[] args){
LinkedHash lineHash = new LinkedHash(333);
for (int i = 0; i < 100; i++) {
DataItem dataItem = new DataItem(i+"_"+i);
lineHash.insert(dataItem);
}
System.out.println("size === "+ lineHash.getSize());
DataItem keyDataItem1 = new DataItem("50_50");
DataItem keyDataItem2 = new DataItem("25_25");
// 查询方法是否有效
System.out.println("get() ==" +lineHash.get(keyDataItem1.hashCode()));
System.out.println("get() ==" +lineHash.get(keyDataItem2.hashCode()));
// 删除方法是否有效
System.out.println("remove == "+lineHash.remove(keyDataItem1.hashCode()));
// 重复删除不会有异常
System.out.println("remove == "+lineHash.remove(keyDataItem1.hashCode()));
// 删除之后，在哈希表中就查找不到了
System.out.println("get() ==" +lineHash.get(keyDataItem1.hashCode()));
// 删除不会影响其他元素。
System.out.println("get() ==" +lineHash.get(keyDataItem2.hashCode()));
System.out.println("get() ==" +lineHash.get(new DataItem("44_44").hashCode()));
System.out.println("size === "+ lineHash.getSize());
}
}
例题：
public class HashTableDemo {
public static void main(String[] args) {
HashTable hashTable = new HashTable(5);
String key="";
Scanner sc=new Scanner(System.in);
while (true){
System.out.println("1.添加 add");
System.out.println("2.遍历 list");
System.out.println("3.删除 del");
System.out.println("4.查找 find");
System.out.println("5.修改 update");
System.out.println("6.退出 exit");
System.out.println("请选择");
key=sc.next();
int id=0;
switch (key){
case "add":{
System.out.println("请输入id");
id=sc.nextInt();
System.out.println("请输入名字");
String name=sc.next();
Employer employer = new Employer(id, name);
hashTable.addIntoHashTable(employer);
break;
}
case "list":{
hashTable.showHashTable();
break;
}
case "del":{
System.out.println("请输入待删除元素的id");
id=sc.nextInt();
hashTable.delHashTable(id);
break;
}
case "find":{
System.out.println("请输入待查找元素的id");
id=sc.nextInt();
hashTable.findHashTable(id);
break;
}
case "update":{
System.out.println("请输入id");
id=sc.nextInt();
System.out.println("请输入名字");
String name=sc.next();
Employer employer = new Employer(id, name);
hashTable.updateHashTable(employer);
break;
}
case "exit":{
System.out.println("退出");
//关流
sc.close();
System.exit(0); //退出
}
default:{
System.out.println("输入有误");
break;
}
}
}
}
}
class HashTable{
private LinkedListEmp[] list;
private int size;
//初始化哈希表
public HashTable(int size) {
this.size=size;
list=new LinkedListEmp[size];
//注意：这里需要分别初始化每一个链表，否则导致数组里
// 面全是null不是LinkedListEmp，从而导致空指针异常
for(int i=0;i<size;i++){
list[i]=new LinkedListEmp();
}
}
//散列函数，用于分配位置
public int hashFun(int id){
//这里直接对哈希表的长度取余
return id%size;
}
//添加
public void addIntoHashTable(Employer emp){
int pos=hashFun(emp.getId());
list[pos].add(emp);
}
//遍历
public void showHashTable(){
for (int i = 0; i < size; i++) {
//遍历数组中的每一个链表
list[i].showList(i);
}
}
//查找
public void findHashTable(int id){
int res = hashFun(id);
Employer emp = list[res].findEmp(id);
if (emp != null) {
System.out.println("找到id为"+id+"的"+emp.getName());
}else{
System.out.println("找不到");
}
}
//根据id删除雇员信息
public void delHashTable(int id){
int res = hashFun(id);
Employer employer = list[res].delEmpById(id);
if(employer==null){
System.out.println("删除失败");
}else {
System.out.println("待删除的员工id为："+id+"姓名是："+employer.getName());
}
}
//根据id修改用户信息
public void updateHashTable(Employer employer){
int res=hashFun(employer.getId());
list[res].updateNode(employer);
}
}
//链表,其中的节点为雇员信息
class LinkedListEmp{
//头指针，默认为空，指向第一个节点，因此这里的头指针是指向数据的
private Employer head=null;
//添加雇员信息
public void add(Employer employer){
//如果是第一个雇员，直接把头指针指向它
if(head==null){
head=employer;
return ;
}
//如果不是第一个雇员，需要定义一个辅助指针，帮助添加
Employer temp=head;
//默认把新的节点按照id大小进行添加
boolean flag=false;//判断id是否已经存在
while(temp.getNext()!=null){
if(temp.getNext().getId()>employer.getId()) {
//找到位置了，就在temp.getNext()前面
break ;
}else if(temp.getNext().getId()==employer.getId()){
flag=true;
break ;
}
temp=temp.getNext();
}
//判断是否已经存在该id
if(flag){
System.out.println("已存在该id，不能重复添加");
return ;
}
//把节点加入到temp.getNext()前面
employer.setNext(temp.getNext());
temp.setNext(employer);
}
//遍历雇员信息
public void showList(int no){
if(head==null){
System.out.println("第"+(no+1)+"条链表为空");
return ;
}
//定义一个指向头结点的辅助节点便于遍历
System.out.println("第"+(no+1)+"条链表信息如下");
Employer temp=head;
while(temp!=null){
System.out.println(temp.getId()+":"+temp.getName());
temp=temp.getNext();
}
}
//查找雇员信息
public Employer findEmp(int id){
if(head==null){
System.out.println("链表为空");
return null;
}
//辅助节点便于查找
Employer employer=head;
while(employer!=null){
if(employer.getId()==id){
break;
}
employer=employer.getNext();
}
return employer;
}
//根据id,删除雇员信息
public Employer delEmpById(int id){
if(head==null){
System.out.println("链表为空");
return null;
}
//辅助节点便于查找
Employer employer=head;
//如果待删除节点为头指针指向的第一个节点
if(head.getId()==id){
//直接把head指向下一个
head=head.getNext();
return employer;
}
while (employer!=null){
//如果待删除元素不是第一个节点
if(employer.getNext()!=null&&employer.getNext().getId()==id){
Employer res=employer.getNext();
employer.setNext(employer.getNext().getNext());
return res;
}
employer=employer.getNext();
}
//没找到
System.out.println("没有待删除元素");
return null;
}
//根据id修改节点信息
public void updateNode(Employer employer){
if(head==null){
System.out.println("链表为空");
return ;
}
Employer temp=head;
while (temp!=null){
if(temp.getId()==employer.getId()){
temp.setName(employer.getName());
System.out.println("修改完成");
return ;
}
temp=temp.getNext();
}
System.out.println("没有找到");
}
}
//雇员节点
class Employer{
private int id;
private String name;
private Employer next;
public Employer(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 Employer getNext() {
return next;
}
public void setNext(Employer next) {
this.next = next;
}
}到这就结束了，如有错误欢迎指正。
全部评论