模拟HashMap类的实现

此例使用数组展示了HashMap的存储实现，刚学集合类框架，希望对初学者有所借鉴，帮助理解HashMap的用法等。此例不免有些许错误，还望各位高手指出。

package com.xiaodpro.util;

/**
 * 模拟HashMap类的实现
 * @author xiaodpro
 * 2010年3月9日
 */
public class MapSet<E,T> implements Set<E,T> {

	private Object[] value;   //键对应的键值
	private Object[] key;     //用户指定键
	private int increment;    //数组动态增加量
	
	/**
	 * 创建一个默认MapSet结构
	 */
	public MapSet() {
		// TODO Auto-generated constructor stub
		this(10);
	}
	
	/**
	 * 创建一个指定初始大小的MapSet结构
	 * 	<p>如果指定大小小于1的话将抛出IllegalArgumentException异常 
	 * @param initSize 初始大小
	 */
	public MapSet(int initSize){
		this(initSize, 10);
	}
	
	/**
	 * 创建一个指定初始大小及增长量的MapSet结构
	 * 	<p>如果初始大小小于1或者是增长量小于1的话将抛出IllegalArgumentException异常
	 * @param initSize 初始大小
	 * @param increment 增长量
	 */
	public MapSet(int initSize, int increment){
		//初始化各个成员变量
		if(initSize < 1 || increment < 1)
			throw new IllegalArgumentException();
			
		this.key = new Object[initSize];
		this.value = new Object[initSize];
		this.increment = increment;
	}

	/**
	 * 向MapSet对象中添加一个键
	 *  <p>如果索引超出当前元素的总数将抛出ArrayIndexOutOfBoundsException异常
	 *  <p>如果key值为null值将会抛出NullPointerException异常
	 *  <p>如果添加的键已经存在于MapSet集合中将会抛出IllegalArgumentException异常
	 * @param key 要添加的键
	 */
	public void add(E key) {
		// TODO Auto-generated method stub
		add(key,null);
	}

	/**
	 * 向MapSet对象中添加一项
	 *  <p>如果索引超出当前元素的总数将抛出ArrayIndexOutOfBoundsException异常
	 *  <p>如果key值为null值将会抛出NullPointerException异常
	 *  <p>如果添加的键已经存在于MapSet集合中将会抛出IllegalArgumentException异常
	 * @param key 要添加的键
	 * @param value 添加的键对应的值
	 */
	public void add(E key, T value) {
		// TODO Auto-generated method stub
		add(key, value, size());
	}
	
	/**
	 * 向MapSet对象的指定位置处添加一项
	 *  <p>如果索引超出当前元素的总数将抛出ArrayIndexOutOfBoundsException异常
	 *  <p>如果key值为null值将会抛出NullPointerException异常
	 *  <p>如果添加的键已经存在于MapSet集合中将会抛出IllegalArgumentException异常
	 * @param key 要添加的键
	 * @param value 键对应的值
	 * @param index 指定的索引
	 */
	public void add(E key, T value, int index){
		//如果添加的值为null值则抛出NullPointerException异常
		if(key == null)
			throw new NullPointerException();
		if(index < 0 || index > size())
			throw new ArrayIndexOutOfBoundsException();
		
		if(isFull()){
			//如果当前长度已达到末端则将当前数组中的数据复制到新的数组中去，并将当前key和value的引用指向新的数组
			Object[] keytmp = new Object[this.key.length + this.increment];
			Object[] valuetmp = new Object[this.key.length + this.increment];
			System.arraycopy(this.key, 0, keytmp, 0, this.key.length);
			this.key = keytmp;
			
			System.arraycopy(this.value, 0, valuetmp, 0, this.value.length);
			this.value = valuetmp;
			removeLast();
		}
		

		for(int j = 0; j < size(); j++){
			//如果存在相同的键值则抛出IllegalArgumentException异常
			if(this.key[j] == key)
				throw new IllegalArgumentException();
		}
		this.key[index] = key;
		this.value[index] = value;
	}

	/**
	 * 移除指定的键
	 *  <p>如果找不到该键将会抛出NullPointerException异常
	 * @param key 要移除的键
	 */
	public T remove(Object key) {
		// TODO Auto-generated method stub
		return delete(spider(key)).search(key);
	}
	
	/**
	 * 删除指定索引处的键
	 *  <p>如果找不到该键值将会抛出ArrayIndexOutOfBoundsException异常
	 * @param index 要删除的索引
	 * @return 被移除的键值
	 */
	@SuppressWarnings("unchecked")
	public MapSet<E,T> delete(int index){
		if(index < 0 || index > size())
			throw new ArrayIndexOutOfBoundsException();
		
		MapSet<E,T> map =  new MapSet<E,T>(1,1);
		map.add((E)key[index], (T)value[index]);
		
		System.arraycopy(key, index + 1, key, index, size() - index);
		System.arraycopy(value, index + 1, value, index, size() - index);
		return map;
	}
	
	/**
	 * 移除最头部的元素
	 *  <p>如果当前MapSet对象没有元素，则抛出NullPointerException异常
	 * @return 移除的元素
	 */
	@SuppressWarnings("unchecked")
	public T removeFirst(){
		if(isEmpty())
			throw new NullPointerException();
		T item = (T)value[0];
		value[0] = null;
		return item;
	}
	
	/**
	 * 移除最尾部的元素
	 *  <p>如果当前MapSet对象中没有元素，则抛出NullPointerException异常
	 * @return 移除的元素
	 */
	@SuppressWarnings("unchecked")
	public T removeLast(){
		if(isEmpty())
			throw new NullPointerException();
		T item = (T)value[size()-1];
		value[size() - 1] = null;
		return item;
	}

	/**
	 * 查找指定键对应的键值
	 * @param item 要查询的键
	 * @return 如果找到该键，则返回该键值；否则返回将抛出NullException异常
	 */
	@SuppressWarnings("unchecked")
	public T search(Object key) {
		// TODO Auto-generated method stub
		try {
			return (T) value[spider(key)];
		} catch (NullPointerException e) {
			// TODO: handle exception
			throw new NullPointerException();
		}
	}
	
	/**
	 * 获取指定索引处的键值
	 *  <p>如果指定的索引超出范围将会抛出ArrayIndexOutOfBoundsException异常
	 * @param index 指定的索引
	 * @return 指定索引处的键值
	 */
	@SuppressWarnings("unchecked")
	public MapSet<E,T> get(int index){
		if(index < 0 || index > size())
			throw new ArrayIndexOutOfBoundsException();
		MapSet<E,T> map = new MapSet<E,T>(1,1);
		map.add((E)key[index], (T)value[index]);
		return map;
	}

	/**
	 * 更新指定键的键值
	 *  <p>如果找不到指定的键将抛出NullPointerException异常
	 * @param key 要更新的键
	 * @param value 新的值
	 */
	public void updateValue(E key, T value) {
		// TODO Auto-generated method stub
		try {
			this.value[spider(key)] = value;
		} catch (NullPointerException e) {
			// TODO: handle exception
			throw new NullPointerException();
		}
	}
	
	private int spider(Object key) throws NullPointerException{
		//查找key键对应的索引，如果找不到该键则抛出NullPointerException异常
		for(int i = 0; i < size(); i++){
			if(this.key[i].equals(key)){
				return i;
			}
		}
		throw new NullPointerException();
	}
	
	/**
	 * 判断当前MapSet对象是否为空,如果为空则返回true,否则返回false
	 * @return 判断结果
	 */
	public boolean isEmpty(){
		if(this.size() == 0)
			return true;
		return false;
		
	}
	
	private boolean isFull(){
		//返回元素数组是否已满
		if(this.size() < this.key.length)
			return false;
		return true;
	}

	/**
	 * 清空当前MapSet对象
	 */
	public void clear() {
		// TODO Auto-generated method stub
		while(!isEmpty())
			key[size()-1] = null;
	}

	/**
	 * 获取当前MapSet对象的大小
	 * @return 当前MapSet对象的有效长度
	 */
	public int size() {
		// TODO Auto-generated method stub
		for(int i = this.key.length - 1; i >= 0; i--){
			if(this.key[i] != null)
				return i + 1;
		}
		return 0;
	}

}

评论

1 楼 陈碧滔 2011-11-21  

消灭零回复！