手写hashmap算法

/**
* 01.自定义一个hashmap
* 02.实现put增加键值对，实现key重复时替换key的值
* 03.重写toString方法，方便查看map中的键值对信息
* 04.实现get方法，根据键对象获取相应的值对象
* 05.封装、增加泛型
* 06.remove方法、数组扩容方法暂缺
* 07.remove方法已增加
*/

package cn.study.lu.four;

public class HashMap <K,V>{

node3[] table;
int size;
public HashMap() {
table = new node3[16];//一般为2的整数次幂
}

public void put(K key,V value) {//定义新的节点对象
//如果要完善，还需要考虑数组扩容，稍后增加

node3 newnode = new node3();
newnode.hash = myHash(key.hashCode(), table.length);
newnode.key = key;
newnode.value = value;
newnode.next = null;

node3 temp = table[newnode.hash];
node3 last = null;
boolean keyRepeat = false;

if (temp == null) {
table[newnode.hash] = newnode;
size++;
}else {//temp不为空的情况下，遍历table[newnode.hash]

while (temp!=null) {
if (temp.key == newnode.key) {
keyRepeat = true;
temp.value = newnode.value;
break;
}else {
last = temp;
temp = temp.next;
}

}
if (!keyRepeat) {
last.next = newnode;
size++;
}

}

public int myHash(int v,int length) {
return v&(length-1);// 也可以用 v % length，但是二者结果不一样，都可以实现散列
}

public String toString() {
StringBuilder sb = new StringBuilder("{");
//遍历数组
for (int i = 0; i < table.length; i++) {
node3 temp = table[i];
//遍历链表
while (temp!=null) {
sb.append(temp.key+":"+temp.value+",");
temp = temp.next;
}

}

sb.setCharAt(sb.length()-1, '}');
return sb.toString();
}

public V get(K key) {
int hash = myHash(key.hashCode(), table.length);
V value = null;

if (table[hash] != null) {
node3 temp = table[hash];

while (temp!=null) {
if (temp.key.equals(key)) {
value = (V)temp.value;
break;
}else {
temp = temp.next;
}

}
}

return value;
}

public void remove(K key) {
int hash = myHash(key.hashCode(), table.length);
node3 temp = table[hash];
node3 copy = null;

if (temp == null) {
return;
}else {
if (temp.next == null) {
table[hash] = null;
temp = null;
size--;
}else {
while (temp.key!=key) {
copy = temp;
temp = temp.next;
System.out.println(temp.value);
}
copy.next = temp.next;
temp = null;
size--;
}

}
}

public static void main(String[] args) {
HashMap<Integer,String> m = new HashMap<Integer,String>();
m.put(1, "aaa");
m.put(2, "bbb");
m.put(3, "ccc");
m.put(4, "ddd");
m.put(5, "eee");

m.put(53, "111");
m.put(69, "222");
m.put(85, "333");

m.put(3, "fff");

m.remove(53);

System.out.println(m);
System.out.println(m.get(69));
}

}

class node2{
int hash;
Object key;
Object value;
node2 next;

}

class node3<K,V>{
int hash;
K key;
V value;
node3 next;
}

巴特西

手写hashmap算法

最新文章

热门文章