java编程进阶小白也能手写HashMap代码

目录

• 什么是HashMap
• HashCode和数组
• Hash碰撞
• toString方法
• 百万级数据压测
  • 步骤 1 来100w条数据，看看要花多久？
  • 步骤 2 设计思路
  • 步骤 3 添加一个size
  • 步骤 4 先设计，后实现
  • 步骤 5 扩容方法
  • 步骤 6 reHash方法
  • 步骤 7 新的问题出现
  • 步骤 8 indexForTable方法
  • 步骤 9 重新转测
  • 步骤 10 再次测试100w数据
  • 步骤 11 PK 原生JDK8的HashMap
• 补丁
  • 步骤 1 put元素的bug
  • 步骤 2 HashMap为什么是无序的？
  • 步骤 3 作业1答案

public class TestMap {
    public static void main(String[] args) {
        Map csts = new HashMap<>();
        csts.put("王大锤",new Customer("王大锤"));
        csts.put("王尼玛",new Customer("王尼玛"));
        csts.put("赵铁柱",new Customer("赵铁柱"));
        //直接根据name拿到对应的实体对象
        Customer customer = (Customer) csts.get("王大锤");
        System.out.println(customer.getName());
    }
}

String a = "abc";
//  97 * 31^(3-1) + 98 * 31^(3-2) + 99 ^ (3-3)
//= 93217 + 3038 + 99 = 96354
System.out.println(a.hashCode());

public class TuziHashMap {
    private Object arr[];
    private int capacity = 20; //初始化容量
    public  TuziHashMap(){
        arr = new Object[capacity];
    }
}

public Object put(String key,Object value){
        //1. 算出HashCode
        int hashCode = key.hashCode();
        //2. 直接取模，得到余数，这个余数就是数组的下标
        int index = hashCode % capacity;
        //3. 将对应的数据放入数组的对应格子
        this.arr[index] = value;
        return  value;

    }

public Object get(String key){
        //1. 算出HashCode
        int hashCode = key.hashCode();
        //2. 直接取模，得到余数，这个余数就是数组的下标
        int index = hashCode % capacity;
        //3. 将对应的数据放入数组的对应格子
        return this.arr[index];
    }

TuziHashMap map = new TuziHashMap();
map.put("王大锤",new Customer("王大锤"));
System.out.println(map.get("王大锤"));

private int hash(String key){
    //return key.hashCode();
    return 10;
}

public Object get(String key){
        //1. 算出HashCode
        int hashCode = hash(key);
        //2. 直接取模，得到余数，这个余数就是数组的下标
        int index = hashCode % capacity;
        //3. 将对应的数据放入数组的对应格子
        return this.arr[index];
    }

TuziHashMap map = new TuziHashMap();
map.put("王大锤",new Customer("王大锤"));
map.put("王尼玛",new Customer("王尼玛"));
System.out.println(map.get("王大锤"));

/**
 * 原来的add方法保留，调用重载的add方法
 * @param object
 * @return
 */
public boolean add(Object object){
	return add(null,object);
}
/**
 * 新增的add方法,增加参数key
 */
public boolean add(Object key,Object object){
	//将数据用节点类包装好，这样才能实现下一个数据的指向
	Node data = new Node(object);
	if(key != null){
		data.key = key;
	}
	//先判断是否是第一个节点
	if(this.firstNode == null){
		this.firstNode = data;
		this.currentNode = data;
	}else{
		//不是第一个节点，就指向当前节点的下一个节点，即currentNode.next
		this.currentNode.next = data;
		//因为已经指向下一个了，所以当前节点也要移动过来
		this.currentNode = data;
	}
	size++;
	return true;

}

TuziHashMap map = new TuziHashMap();
map.put("王大锤",new Customer("王大锤"));
map.put("王尼玛",new Customer("王尼玛"));
System.out.println(map.get("王大锤"));

Customer{name=‘王大锤", sex=‘null", birthDate=‘null", phoneNumber=‘null", status=0}

public String toString(){
    StringBuffer sb = new StringBuffer("[
");
    for (int i = 0; i < arr.length; i++) {
        LinkedList list = arr[i];
        if(list != null){
            while(list.hasNext()){
                Node node = list.nextNode();
                sb.append(String.format("	{%s=%s}",node.key,node.data));

                if(list.hasNext())
                    sb.append(",
");
                else
                    sb.append("
");
            }
        }
    }
    sb.append("]");
    return sb.toString();
}

long startTime = System.currentTimeMillis();     //获取开始时间
TuziHashMap map = new TuziHashMap();
for (int i = 0; i < 100000; i++) {
    map.put("key" + i, "value--" + i);
}
System.out.println(map);
long overTime = System.currentTimeMillis();      //获取结束时间
System.out.println("程序运行时间为："+(overTime-startTime)+"毫秒");

private void enlarge() {
    capacity *= 2; // 等同于 capacity = capacity * 2 ，这么写只是因为我想装个逼。
    LinkedList[] newArr = new LinkedList[capacity];
    System.out.println("数组扩容到" + capacity);
    int len = arr.length; //把arr的长度写在外面，这样能减少一丢丢的计算
    for (int i = 0; i < len; i++) {
        LinkedList linkedList = arr[i];
        if(arr[i] != null){
            while(linkedList.hasNext()){
                Node node = linkedList.nextNode();
                Object key = node.key;
                Object value = node.data;
                //将原有的数据一个个塞到新的数组
                reHash(newArr,key,value);
            }
        }
    }
    //新数组正式上位
    this.arr = newArr;
}

private void reHash(LinkedList[] newArr, Object key, Object value) {
    //1. 算出HashCode
    int hashCode = hash(key.toString());
    //2. 直接取模，得到余数，这个余数就是数组的下标
    int index = hashCode % capacity ;
    //3. 将对应的数据放入数组的对应格子
    if(newArr[index] == null){
        newArr[index] = new LinkedList();
    }
    newArr[index].add(key,value);
}

long startTime = System.currentTimeMillis();     //获取开始时间
TuziHashMap map = new TuziHashMap();
for (int i = 0; i < 260; i++) {
    map.put("key" + i, "value--" + i);
}
System.out.println(map);
long overTime = System.currentTimeMillis();      //获取结束时间
System.out.println("程序运行时间为："+(overTime-startTime)+"毫秒");

private int indexForTable(int hashCode) {
    return hashCode & Integer.MAX_VALUE % capacity;
}

long startTime = System.currentTimeMillis();     //获取开始时间
TuziHashMap map = new TuziHashMap();
for (int i = 0; i < 100 * 10000; i++) {
    map.put("key" + i, "value--" + i);
}
System.out.println(map.get("key" + 99999));
long overTime = System.currentTimeMillis();      //获取结束时间
System.out.println("程序运行时间为："+(overTime-startTime)+"毫秒");

long startTime = System.currentTimeMillis();     //获取开始时间
HashMap map = new HashMap();
for (int i = 0; i < 100 * 10000; i++) {
    map.put("key" + i, "value--" + i);
}
System.out.println(map.get("key" + 99999));
long overTime = System.currentTimeMillis();      //获取结束时间
System.out.println("程序运行时间为："+(overTime-startTime)+"毫秒");

map.get("a")

public Object put(String key,Object value){
    if(size > capacity){
        enlarge();
    }
    //1. 算出HashCode
    int hashCode = hash(key);
    //2. 直接取模，得到余数，这个余数就是数组的下标
    int index = indexForTable(hashCode);
    //3. 将对应的数据放入数组的对应格子
    if(this.arr[index] == null){
        this.arr[index] = new LinkedList();
    }
    LinkedList linkedList = this.arr[index];
    if(linkedList.size() == 0){
        linkedList.add(key,value);
    }
    //遍历这个node的链表，如果发现重复key，直接覆盖
    Node firstNode = linkedList.firstNode;
    Node node = firstNode;
    while(node != null){
        if(node.key.equals(key)){
            node.data = value;
        }
        node = node.next;
    }
    this.size++;
    return value;
}