简单模拟一下HashMap的实现
程序员文章站
2022-05-21 15:17:13
...
- hashMap的实现是由数组和链表,数据结构是"链表散列"
1.准备数据 实体类Info
package com.gwzan.map; /** * 员工信息类 * @author zan * */ public class Info { private String key; private String name; public Info(String key,String name){ this.key=key; this.name=name; } public String getKey() { return key; } public void setKey(String key) { this.key = key; } public String getName() { return name; } public void setName(String name) { this.name = name; } }
2.结点
package com.gwzan.map; /** * 链接点 ,相当于是车厢 * @author zan * */ public class Node { public Info info; //数据域 public Node next; //指针域 public Node(Info info){ this.info=info; } }
3.链表
package com.gwzan.map; /** * 链表,相当于火车 * @author zan * */ public class LinkList { private Node first;//头结点 public LinkList(){ first=null ;//初始化 } /** * 插入数据,在头结点之后进行插入 */ public void insertFirst(Info info){ Node node=new Node(info); node.next=first; first=node; } /** * 删除一个结点,在头节点后进行删除 */ public Node deleteFirst(){ Node tmp=first; first=tmp.next; return tmp; } /** * 查找方法 */ public Node find(String key){ Node current=first; while (!key.equals(current.info.getKey())) { if (current.next==null) { return null; } current=current.next; } return current; } /** * 删除方法,根据数据域进行删除 */ public Node delete(String key){ Node current =first; Node previous=first; while (!key.equals(current.info.getKey())) { if (current.next==null) { return null; } previous=current; current=current.next; } if (current==first) { first=first.next; }else { previous.next=current.next; } return current; } }
4.hashmap类
package com.gwzan.map; import java.math.BigInteger; /** * 哈希表——链地址法: * 哈希表每个单元设置链表,某个数据项的关键字还是像通常一样映射到哈希表的单元中, * 而数据项本身是插入到单元的链表中 * @author zan * */ public class HashMap { private LinkList[] arr; public HashMap(){ arr=new LinkList[100]; } public HashMap(int maxsize){ arr=new LinkList[maxsize]; } /** * 插入数据 * @param info */ public void insert(Info info){ //获得关键字 String key=info.getKey(); //关键字所自定的哈希数 int hashVal=hashCode(key); if (arr[hashVal]==null) { arr[hashVal]=new LinkList(); } arr[hashVal].insertFirst(info); } /** * 查找数据 */ public Info find(String key){ int hashVal=hashCode(key); return arr[hashVal].find(key).info; } /** * 删除数据 */ public Info delete(String key){ int hashVal=hashCode(key); return arr[hashVal].delete(key).info; } //解决哈希冲突的 public int hashCode(String key){ BigInteger hashVal=new BigInteger("0"); BigInteger pow27=new BigInteger("1"); for (int i = key.length()-1; i >=0; i--) { int letter=key.charAt(i)-96; BigInteger letterB=new BigInteger(String.valueOf(letter)); hashVal=hashVal.add(letterB.multiply(pow27)); pow27=pow27.multiply(new BigInteger(String.valueOf(27))); } return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue(); } }
5.测试类
package com.gwzan.map; public class TestHashMap { public static void main(String[] args) { //HashMap hashMap=new HashMap(10000); HashMap hashMap=new HashMap(); hashMap.insert(new Info("a", "张三")); hashMap.insert(new Info("ct", "李四")); hashMap.insert(new Info("b", "王五")); System.out.println(hashMap.find("a").getName()); System.out.println(hashMap.find("ct").getName()); System.out.println(hashMap.find("b").getName()); System.out.println(hashMap.hashCode("a")); System.out.println(hashMap.hashCode("ct")); System.out.println(hashMap.delete("b").getName()); //System.out.println(hashMap.find("b").getName()); } }
上一篇: 工作一年后迎来第一次跳槽