手写HashMap

朴灿烈づ我的快乐病毒、 2021-12-04 09:31 318阅读 0赞

## 1.定义Map接口 ##

public interface Map<K, V> {
    
    	//设置值
    	public V put(K k, V v);
    	//取值
    	public V get(K k);
    	
    }

## 2.Entry链表 ##

public class Entry<K, V> {
    
    	K k;
    
    	V v;
    
    	Entry<K, V> next;
    	
    	/**
         *   在next指向下一个节点
    	 */
    	public Entry(K k, V v, Entry<K, V> next) {
    		this.k = k;
    		this.v = v;
    		this.next = next;
    	}
    
    	public K getKey() {
    		return k;
    	}
    
    	public V getValue() {
    		return v;
    	}
    
    }

## 3.实现Map接口 ##

public class HashMap<K, V> implements Map<K, V> {
    
    	// 数组默认长度
    	private int defaultLength;
    
    	// 默认负载因子
    	private double defaultAddFactor;
    
    	// 使用长度
    	private double useSize;
    
    	// entry数组
    	Entry<K, V>[] entrys;
    
    	/**
    	 * 有参构造器，传入长度，负载因子
    	 * 
    	 * @param defaultLength
    	 *            数组长度
    	 * @param defaultAddFactor
    	 *            负载因子
    	 */
    	public HashMap(int defaultLength, double defaultAddFactor) {
    		if (defaultLength < 0) {
    			throw new RuntimeException("长度错误");
    		}
    
    		if (defaultAddFactor <= 0 || Double.isNaN(defaultAddFactor)) {
    			throw new RuntimeException("负载因子错误");
    		}
    
    		this.defaultLength = defaultLength;
    		this.defaultAddFactor = defaultAddFactor;
    		entrys = new Entry[this.defaultLength];
    	}
    
    	/**
    	 * 无参构造器，默认传16 0.75
    	 */
    	public HashMap() {
    		this(16, 0.75);
    	}
    
    	/**
    	 * 计算hashcode
    	 * 
    	 * @param hashCode
    	 * @return
    	 */
    	private int hash(int hashCode) {
    
    		hashCode = hashCode ^ ((hashCode >>> 20) ^ (hashCode >>> 12));
    		return hashCode ^ ((hashCode >>> 7) ^ (hashCode >>> 4));
    	}
    
    	/**
    	 * 获取保存位置的数组下标
    	 */
    	private int getIndex(K k, int length) {
    		int m = length - 1;
    		int index = hash(k.hashCode()) & m;
    		return index > 0 ? index : -index;
    	}
    
    	@Override
    	public V put(K k, V v) {
    
    		// 判断是否需要库容
    		if (this.useSize > this.defaultAddFactor * this.defaultLength) {
    			this.dilatation();
    		}
    
    		// 计算出当前下标
    		int index = this.getIndex(k, this.defaultLength);
    
    		// 获取下标上的entry
    		Entry<K, V> entry = this.entrys[index];
    
    		// 创建一个新的 newentry
    		Entry<K, V> newentry = new Entry<K, V>(k, v, null);
    
    		// 判断当前下标是否被使用，如果没有被使用就将newentry填入
    		if (entry == null) {
    			this.entrys[index] = newentry;
    			// 使用后 使用长度+1
    			this.useSize++;
    		} else {
    			// -否则
    
    			Entry<K, V> e = entry;
    			// --判断当前key是否等于传入的k
    			if (e.getKey() == k) {
    				// --如果相等，就将传入v赋值给e.v
    				e.v = v;
    			} else {
    				// ---如果不相等，就循环遍历entry的下一个entry .next，
    				while (e.next != null) {
    					// ---判断下一个entry的key是否等于传入的k，如果相等就赋值v，
    					if (e.next.getKey() == k || e.next.getKey().equals(k)) {
    						e.next.v = v;
    						break;
    					} else {
    						e = e.next;
    					}
    				}
    
    				// ----判断上边循环后entry.next 是否等于null，如果等于null
    				// ----将newentry设置到entry.next的位置
    				if (e.next == null) {
    					e.next = newentry;
    				}
    			}
    		}
    
    		// 返回newentry.getValue()
    		return newentry.getValue();
    	}
    
    	@Override
    	public V get(K k) {
    
    		// 获取当前下标
    		int index = this.getIndex(k, this.entrys.length);
    
    		// 得到下标上的entry
    		Entry<K, V> entry = this.entrys[index];
    
    		// entry非空校验
    		if (entry == null) {
    			throw new NullPointerException("空空如也");
    		}
    
    		// 循环entry != null
    		while (entry != null) {
    			// key相等就返回
    			if (entry.getKey() == k || entry.getKey().equals(k)) {
    				return entry.getValue();
    			} else {
    				// 如果不相等，将next赋值给entry继续循环
    				entry = entry.next;
    			}
    		}
    
    		// 找不到就返回null
    		return null;
    	}
    
    	/**
    	 * 扩容
    	 */
    	private void dilatation() {
    
    		// 创建一个新的entry数组 ，长度为 defualtLength*2
    		Entry<K, V>[] newEntryTable = new Entry[this.defaultLength * 2];
    
    		// 创建一个list 用来存放entry
    		List<Entry<K, V>> entryList = new ArrayList<Entry<K, V>>();
    
    		// 1.先将历史的数据保存
    		// 循环entry数组
    		for (int i = 0; i < entrys.length; i++) {
    			Entry<K, V> entry = entrys[i];
    			// 判断数组下标上的entry!=null
    			while (entry != null) {
    				entryList.add(entry);
    				// 将enrty存到list中，entry = entry.next;
    				entry = entry.next;
    			}
    		}
    
    		// 非空校验list
    		if (entryList != null && entryList.size() > 0) {
    			// 重新设置默认长度
    			this.defaultLength = this.defaultLength * 2;
    			// 使用长度重置为0
    			this.useSize = 0;
    			// 将newtable赋值给table
    			this.entrys = newEntryTable;
    			// 2.将保存好的数据存到新的容器中
    			for (Entry<K, V> entry : entryList) {
    				// 循环list中的entry，并将其next置位null
    				if (entry.next != null) {
    					entry.next = null;
    				}
    				// 调用put方法,传入entry.k entry.v
    				put(entry.getKey(), entry.getValue());
    			}
    		}
    	}
    
    }

## 4.测试类 ##

public class Test {
    
    	public static void main(String[] args) {
    
    		Map<String,Integer> map = new HashMap<String,Integer>();
    		for(int i=0;i<10000;i++){
    			map.put(""+i, i);
    		}
    		
    		for(int i=0;i<10000;i++){
    			System.out.println("\t key:"+i+"\t value:"+map.get(""+i));
    		}
    	}
    
    }