Java实现简易HashMap功能详解

Java实现简易HashMap功能详解

本文实例讲述了java实现简易HashMap功能。分享给大家供大家参考，具体如下：

创建节点类

节点类含有的属性：键值对（value，key）以及指向下一节点的next；

这些属性的get以及set方法

代码如下：

/**

* 节点类

* @author HP

*

*/

public class Node {

private Object value;

private Object key;

private Node next;

/**

* 空节点

*/

public Node() {

}

/**

* 值为key value的节点

* @param data

*/

public Node(Object key,Object value) {

this.key = key;

this.value = value;

}

//接下来就是一些数据和节点的set，get

public Object getValue() {

return value;

}

public void setValue(Object value) {

this.value = value;

}

public Object getKey() {

return key;

}

public void setKey(String key) {

this.key = key;

}

public Node getNext() {

return next;

}

public void setNext(Node next) {

this.next = next;

}

}

实现MyHash

实现MyHash的基本操作：

实现哈希表的基本存取运算

1.创建一个固定大小数组

2.将数组中的每个元素作为头节点

存储键值对

3.存数：通过对key某种运算，计算出该数的哈希码，将该哈希码与数组做某种运算，得到该数在数组中的哪一个位置下的链表中

4.取数：计算该数的哈希码，然后同样找到该数在数组中的位置，然后从该头节点依次向下进行比较得到该数，不存在则返回null

HashMap的源代码以及函数使用方法及返回值：

HashMap hash = new HashMap();

hash.keySet()

hash.hashCode() :返回int类型

hash.put(Object key, Object value)

hash.get(Object key)返回key值对应的value

hash.remove(key) 返回对应的value

hash.remove(key, value) 返回boolean是否remove成功

hash.size() :返回int类型的存储的节点的个数

hash.containsKey(Object key) :boolean

hash.containsValue(value) :boolean

hash.values() :返回value集合

hash.clear();

hash.replace(key, oldValue, newValue) ???

hash.replace(key, value) 将key对应的oldvalue换为传入的参数value，返回oldvalue

hash.entrySet()

hash.isEmpty()

hash.equals(o)：判断两个对象是否相等，看系统源代码，可重写

遍历Iterator输出的是所有节点对应的value的值

存储的东西越来越大，那么删除插入操作越来越复杂,那么需要rehash（需要一个条件判断是否需要rehash）

本次示例没有编写rehash函数。

MyHash代码，注释还比较详细，后边还有测试代码以及测试结果：

public class MyHash {

//哈希数组的长度初始化为8

private int size = 8;

private int number = 0;//存储的节点的个数

//哈希数组

private ArrayList array_head = new ArrayList(size);

//构造方法

public MyHash() {

for(int i=0;i

LinkedList mylist = new LinkedList();//哈希数组中初始化存储的为空链表头

array_head.add(mylist);//初始化的时候就将空节点头添加到数组中去

}

}

/**

* 根据 键值对 生成节点

* 将节点放入哈希表中

* @param key 键

* @param value 值

*/

public void put(Object key,Object value) {

if(number/size == 10) {

rehash();

}

number++;

Node new_node = new Node(key,value);//由传入的参数生成新节点

int code = hashcode(key.toString());//得到哈希码

int position = locate(code);//得到该哈希码所对应的哈希数组中的位置

//找到该位置对应的链表头

LinkedList list_head = (LinkedList) array_head.get(position);

//将节点放入哈希表中

list_head.add(new_node);

}

/**

*

*/

private void rehash() {

}

/**

* @param key

* @param value

* @return 返回键值对应得节点

*/

public Object get(Object key) {

int code = hashcode(key.toString());//得到哈希码

int position = locate(code);//得到该哈希码所对应的哈希数组中的位置

//找到该位置对应的链表

LinkedList list_head = (LinkedList) array_head.get(position);

//从头遍历链表 ，找到与键key对应的节点的value值进行输出

for(int i=0;i

//首先拿到头节点

Node head = (Node) list_head.get(i);

Node node = head;

while(node!=null) {

//如果 键 相等

if(node.getKey().equals(key)) {

// System.out.println("node.getValue() :"+node.getValue());

return node.getValue();

}

node = node.getNext();

}

}

return null;//否则返回空

}

/**

* 移除键为key的节点

* @param key

* @return 返回删除节点的key对应的value

*/

public Object remove(Object key) {

number--;

int code = hashcode(key.toString());//得到哈希码

int position = locate(codmLIxaMe);//得到该哈希码所对应的哈希数组中的位置

//找到该位置对应的链表

LinkedList list_head = (LinkedList) array_head.get(position);

//从头遍历链表 ，找到与键key对应的节点的value值进行输出

for(int i=0;i

//首先拿到头节点

Node head = (Node) list_head.get(i);

Node node = head;

while(node!=null) {

//如果 键 相等

if(node.getKey().equals(key)) {

Object value = node.getValue();

list_head.remove(node);

return value;

}

node = node.getNext();

}

}

return null;//否则返回空

}

public Object replace(Object key,Object newvalue) {

System.out.println("replace");

int code = hashcode(key.toString());//得到哈希码

int position = locate(code);//得到该哈希码所对应的哈希数组中的位置

//找到该位置对应的链表

LinkedList list_head = (LinkedList) array_head.get(position);

//从头遍历链表 ，找到与键key对应的节点的value值进行输出

for(int i=0;i

//首先拿到头节点

Node head = (Node) list_head.get(i);

Node node = head;

while(node!=null) {

//如果 键 相等

if(node.getKey().equals(key)) {

Object oldvalue = node.getValue();

node.setValue(newvalue);

return oldvalue;

}

node = node.getNext();

}

}

return null;//否则返回空

}

/**

* @param key

* @return 哈希表中含有该key，返回true

*/

public boolean containsKey(Object key) {

int code = hashcode(key.toString());//得到哈希码

int position = locate(code);//得到该哈希码所对应的哈希数组中的位置

//找到该位置对应的链表

LinkedList list_head = (LinkedList) array_head.get(position);

//从头遍历链表 ，找到与键key对应的节点的value值进行输出

for(int i=0;i

//首先拿到头节点

Node head = (Node) list_head.get(i);

Node node = head;

while(node!=null) {

//如果 键 相等

if(node.getKey().equals(key)) {

return true;

}

node = node.getNext();

}

}

return false;//否则返回空

}

public Object containsValue(Object value) {

//找到该位置对应的链表

for(int k=0;k

LinkedList list_head = (LinkedList) array_head.get(k);

//从头遍历链表 ，找到与键key对应的节点的value值进行输出

for(int i=0;i

//首先拿到头节点

Node head = (Node) list_head.get(i);

Node node = head;

while(node!=null) {

//如果 键 相等

if(node.getValue().equals(value)) {

return true;

}

node = node.getNext();

}

}

}

return false;//否则返回空

}

/**

* 打印哈希表

*/

public void show() {

System.out.println("打印哈希表");

for(int i=0;i

LinkedList list_head = array_head.get(i);//得到链表头

System.out.println("链表 ："+(i+1));

for(int j=0;j

Node head = (Node) list_head.get(j);//取出每个节点

Node node = head;

while(node!=null) {

//打印出每个节点得键值对

System.out.print("节点"+(j+1)+" :("+node.getKey()+":"+node.getValue()+")"+"-->");

node = node.getNext();

}

}

System.out.println();

}

System.out.println();

}

/**

*

* @return 返回存储的节点的个数

*/

public int size() {

return number;

}

/**

* 清除哈希表中的所有元素

*/

public void clear() {

for(int i=0;i

LinkedList list_head = array_head.get(i);//得到链表头

list_head.clear();

}

number = 0;

}

/**

* 计算字符串的哈希码

* ASCII码相加

*mLIxaM @param s

* @return

*/

public int hashcode(String s) {

int k = 0;

for(int i=0;i

k += s.charAt(i);

}

return k;

}

/**

* 得到哈希码对应在数组中的位置

* @param k

* @return

*/

public int locate(int k) {

int m = k%size;

return m;

}

}

测试代码及结果

public class Test {

public static void main(String[] args) {

MyHash myhash = new MyHash();

myhash.put("abc", 123);

myhash.put("b", 2);

myhash.put("c", 3);

myhash.put("a", 1);

myhash.put("d", 4);

myhash.put("e", 5);

myhash.put("f", 6);

myhash.put("g", 7);

myhash.put("h", 8);

myhash.put("i", 9);

myhash.put("j", 10);

myhash.put("k", 11);

myhash.put("l", 12);

myhash.put("m", 13);

System.out.println("myhash.get(\"g\") :"+myhash.get("g"));

System.out.println("myhash.size() :"+myhash.size());

System.out.println("myhash.replace(\"m\", 20) :"+myhash.replace("m", 20));

System.out.println("myhash.containsValue(5) :"+myhash.containsValue(5));

System.out.println("myhash.containsKey(\"g\") :"+myhash.containsKey("g"));

System.out.println("myhash.remove(\"j\") :"+myhash.remove("j"));

System.out.println("myhash.show()");

myhash.show();

myhash.clear();

System.out.println("myhash.clear()");

System.out.println("myhash.size() :"+myhash.size());

}

}

更多java相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。