手动实现在个HashMap

自己实现了一个hashMap, 有兴趣的可以研究下。

从开始构思到完成，大概花了40分钟。命名就有点随意，主要是用于练习。

有兴趣的，可以将Object 改成 泛型，这样适应性更好，不用强转了。

代码如下：

查看代码 

import java.util.ArrayList;
import java.util.List;

/**
 * 手动实现一个 Map
 * 包括
 *
 */


public class MyHashMap {

    private int length = 16; // 数组长度
    public int size = 0;   // 大小
    private KeyAndValue[]  objects = new KeyAndValue[16];

    // 增
    public void put(Object key, Object value) {
        if (key == null || value == null) {
            throw new RuntimeException("添加出问题，key 或value 不能为空");
        }

        KeyAndValue newKeyAndValue = new KeyAndValue(key, value);
        // 如果 拥有的元素大小 少于数组长度，则不用增长
        if (size < length - 1) {
            size = size + addOneObject(newKeyAndValue);
        } else {
            // 复制数据
            copyArray();
            size = size + addOneObject(newKeyAndValue);
        }
    }

    // 添加一个对象
    private int addOneObject(KeyAndValue newKeyAndValue) {
        int index = newKeyAndValue.index();
        Object object = objects[Math.abs(index % length)];
        if (object == null) {
            objects[Math.abs(index % length)] = newKeyAndValue;
            return 1;
        } else {
            return ((KeyAndValue) object).add(newKeyAndValue);
        }
    }

    // 将数据加倍
    private void copyArray() {
        final KeyAndValue[] newArray = new KeyAndValue[length * 2];
        final KeyAndValue[] oldArray = objects;
        objects = newArray;
        length = length * 2;
        System.out.println(" 扩容 ");

        // 遍历 oldArray, 将元素添加到 newArray 中
        for (Object o : oldArray) {
            if (o == null) continue;
            addMoreObjects((KeyAndValue) o);
        }
    }

    // 添加一个对象，并也添加其下一个对象
    private void addMoreObjects(KeyAndValue keyAndValue) {
        addOneObject(keyAndValue);
        if (keyAndValue.next != null) {
            addMoreObjects(keyAndValue.next);
        }
    }

    // 删
    public void del(Object key) {
        final KeyAndValue object = (KeyAndValue) (objects[KeyAndValue.index(key) % length]);
        if (object == null) {
            // 说明没有这个元素
            return;
        }
        // 刚好第一个是这个元素，则将第一个元设置为这个元素的下一个元素
        if (object.key.equals(key)) {
            objects[KeyAndValue.index(key) % length] = object.next;
            size--;
            return;
        }

        // 否则在链表上删除
        size = size - object.del(key);
    }

    // 查
    public Object get(Object key) {
        KeyAndValue object = (KeyAndValue) (objects[KeyAndValue.index(key) % length]);
        if (object == null) {
            return null;
        }
        return object.get(key);
    }

    // 遍历
    public List getAll() {
        final ArrayList list = new ArrayList<>();
        for (KeyAndValue object : this.objects) {
            if(object==null) continue;
            object.putToList(list);
        }
        return list;

    }


}

// 这个是存key和value 的链表
class KeyAndValue {
    Object key;
    Object value;
    KeyAndValue next;

    int index() {
        return Math.abs(key.hashCode());
    }

    static int index(Object o) {
        return Math.abs(o.hashCode());
    }

    public KeyAndValue(Object key, Object value) {
        this.key = key;
        this.value = value;
    }

    // 递归处理
    public int add(KeyAndValue newKeyAndValue) {
        // 相同的则替换
        if (key.equals(newKeyAndValue.key)) {
            value = newKeyAndValue.value;
            return 0;
        }
        // 不同的key,没有下一个
        if (next == null) {
            next = newKeyAndValue;
            return 1;
        }
        // 不同的key,且有下一个
        return next.add(newKeyAndValue);
    }

    public int del(Object key) {
        if (next == null) {
            return 0;
        }
        // 如果下一个元素就是要删除元素，则将next 指向下下个元素
        if (next.key.equals(key)) {
            next = next.next;
            return 1;
        }
        return next.del(key);
    }

    public Object get(Object getKey) {
        if (key.equals(getKey)) {
            return value;
        }
        if (next == null) {
            return null;
        }
        return next.get(getKey);
    }

    public void putToList(ArrayList list) {
        list.add(this);
        if (next != null) {
            next.putToList(list);
        }
    }

    @Override
    public String toString() {
        return "KeyAndValue{" +
                "key=" + key +
                ", value=" + value +
                '}';
    }
}

						  
					  
						
							


						

							
							
			代码Demo							
						



						

						
						


						

						
					
					

					
					

						
相关

						

				
						
			            
            
            
                                    
           
  			
						

					

					
				

				

														
					
					

					
									

					
									   
标签

										

										
    
										

									

										
										

									

					

					
				


			
		
		
		
			


						





	

	
一品网 冀ICP备14022925号-6