【Java数据结构】自己实现一个HahMap（实现其put, toString, get方法）

HashMap

HashMap存储的是：键值对 (key, value)

HashMap的Key可以冲突，在冲突时，覆盖原有的Key对应的Value值。
下面是一个Key冲突的例子，运行效果如下：

目标位置相同时，节点形成链表。如下

代码（一共三个版本，最终版在最下面）

• 版本一：put方法

MyHashMap.java

package cn.hanquan.file;public class MyHashMap {Node[] table;// 位桶数组int size;// 存放键值对的个数public MyHashMap() {table = new Node[16];}public void put(Object key, Object value) {// 定义新节点对象Node newNode = new Node();newNode.hash = myHash(key.hashCode(), table.length);newNode.key = key;newNode.value = value;newNode.next = null;Node temp = table[newNode.hash];// 用来检查位置是否被占用Node last = null;// 临时存储上一个节点if (temp == null) {// 未占用table[newNode.hash] = newNode;} else {// 被占用while (temp != null) {if (temp.key.equals(key)) {// 重复System.out.println("key重复: key=" + key + ",value=" + value);temp.value = value;// 覆盖value, 而hash, key, next保持不变return;} else {// 不重复last = temp;// 小弟踩着大哥脚印temp = temp.next;// 大哥先走一步}}last.next = newNode;}}public static void main(String[] args) {MyHashMap h = new MyHashMap();System.out.println("长度：" + h.table.length);h.put(10, "aa");h.put(20, "bb");h.put(30, "cc");h.put(20, "ssss");System.out.println("执行完毕");}// 计算放入那个桶public int myHash(int v, int length) {System.out.println("hash=" + (v % length));return v % length;} }

Node.java

package cn.hanquan.file;public class Node {int hash;Object key;Object value;Node next; }

---

• 版本二：添加 toString 方法

Node.java

package cn.hanquan.file;public class Node {int hash;Object key;Object value;Node next; }

MyHashMap.java

package cn.hanquan.file;/** 实现put方法，增加一个元素* 实现toString方法，仿版查看map中的键值对信息*/ public class MyHashMap {Node[] table;// 位桶数组int size;// 存放键值对的个数public MyHashMap() {table = new Node[16];}public void put(Object key, Object value) {// 定义新节点对象Node newNode = new Node();newNode.hash = myHash(key.hashCode(), table.length);// System.out.println("key=" + key + "hashCode=" + key.hashCode());newNode.key = key;newNode.value = value;newNode.next = null;Node temp = table[newNode.hash];// 用来检查位置是否被占用Node last = null;// 临时存储上一个节点if (temp == null) {// 未占用table[newNode.hash] = newNode;} else {// 被占用while (temp != null) {if (temp.key.equals(key)) {// 重复System.out.println("key重复: key=" + key + ",value=" + value);temp.value = value;// 覆盖value, 而hash, key, next保持不变return;} else {// 不重复last = temp;// 小弟踩着大哥脚印temp = temp.next;// 大哥先走一步}}last.next = newNode;}}public String toString() {StringBuilder sb = new StringBuilder("{");for (int i = 0; i < table.length; i++) {Node temp = table[i];while (temp != null) {// 遍历链表sb.append("[" + i + "]" + temp.key + "->" + temp.value + ",");// 不纠结最后多余的逗号,后面直接替换成}就行temp = temp.next;}}sb.setCharAt(sb.length() - 1, '}');return sb.toString();}public static void main(String[] args) {MyHashMap h = new MyHashMap();System.out.println("长度：" + h.table.length);h.put(10, "aa");System.out.println(h.toString());h.put(20, "bb");System.out.println(h.toString());h.put(30, "cc");System.out.println(h.toString());h.put(20, "dd");System.out.println(h.toString());h.put(53, "ee");System.out.println(h.toString());h.put(69, "ff");System.out.println(h.toString());h.put(85, "gg");System.out.println(h.toString());}// 计算放入那个桶public int myHash(int v, int length) {// System.out.println("hash=" + (v % length));return v % length;} }

运行结果

长度：16
{[10]10->aa}
{[4]20->bb,[10]10->aa}
{[4]20->bb,[10]10->aa,[14]30->cc}
key重复: key=20,value=dd
{[4]20->dd,[10]10->aa,[14]30->cc}
{[4]20->dd,[5]53->ee,[10]10->aa,[14]30->cc}
{[4]20->dd,[5]53->ee,[5]69->ff,[10]10->aa,[14]30->cc}
{[4]20->dd,[5]53->ee,[5]69->ff,[5]85->gg,[10]10->aa,[14]30->cc}

---

• 版本三：增加 get 方法

Node.java

package cn.hanquan.file;public class Node {int hash;Object key;Object value;Node next; }

MyHashMap.java

package cn.hanquan.file;/** 实现put方法，增加一个元素* 实现toString方法，仿版查看map中的键值对信息* 实现get方法，通过键对象查找相对应的值对象*/ public class MyHashMap {Node[] table;// 位桶数组int size;// 存放键值对的个数public MyHashMap() {table = new Node[16];}public void put(Object key, Object value) {// 定义新节点对象Node newNode = new Node();newNode.hash = myHash(key.hashCode(), table.length);// System.out.println("key=" + key + "hashCode=" + key.hashCode());newNode.key = key;newNode.value = value;newNode.next = null;Node temp = table[newNode.hash];// 用来检查位置是否被占用Node last = null;// 临时存储上一个节点if (temp == null) {// 未占用table[newNode.hash] = newNode;size++;} else {// 被占用while (temp != null) {if (temp.key.equals(key)) {// 重复System.out.println("key重复: key=" + key + ",value=" + value);temp.value = value;// 覆盖value, 而hash, key, next保持不变return;} else {// 不重复last = temp;// 小弟踩着大哥脚印temp = temp.next;// 大哥先走一步}}last.next = newNode;size++;}}public String toString() {StringBuilder sb = new StringBuilder("{");for (int i = 0; i < table.length; i++) {Node temp = table[i];while (temp != null) {// 遍历链表sb.append("[" + i + "]" + temp.key + "->" + temp.value + ",");// 不纠结最后多余的逗号,后面直接替换成}就行temp = temp.next;}}sb.setCharAt(sb.length() - 1, '}');return sb.toString();}public Object get(Object key) {int hash = MyHashMap.myHash(key.hashCode(), table.length);Node t = table[hash];while (t != null) {if (key == t.key)return t.value;elset = t.next;}System.out.println("你要查找的key不存在！");return null;}public static void main(String[] args) {MyHashMap h = new MyHashMap();h.put(10, "aa");h.put(20, "bb");h.put(30, "cc");h.put(20, "dd");h.put(53, "ee");h.put(69, "ff");h.put(85, "gg");System.out.println(h.toString());System.out.println(h.get(30));}// 计算放入那个桶public static int myHash(int v, int length) {// System.out.println("hash=" + (v % length));return v % length;} }

总结

以上是生活随笔为你收集整理的【Java数据结构】自己实现一个HahMap（实现其put, toString, get方法）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。