/**
* 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;
}