java数据结构 hashmap开放地址法

采用压缩可选值后，容易产生相同的hashCode，如a==ct

开放地址法：当冲突发生时，通过依次查找数组的一个空位，将数据填入。

1、插入数据

<pre name="code" class="java">	/*
	 * 插入数据
	 */
	public void insert(Info info){
		//获得关键字
		String key=info.getKey();
		//关键字对应的哈希数
		int hashVal=hashCode(key);
		//如果arr[hashVal]没被占用过，或占用过但已删除
		while(arr[hashVal]!=null&&arr[hashVal].getName()!=null){
			hashVal++;
			hashVal%=arr.length;
		}	
		arr[hashVal]=info;
	}

2、查找数据

	/*
	 * 查找数据
	 */
	public Info find(String key){
		int hashVal=hashCode(key);
		while(arr[hashVal]!=null){
			if(arr[hashVal].getKey().equals(key)){
				return arr[hashVal];
			}
			hashVal++;
			hashVal%=arr.length;
		}
		return null;
	}

3、删除数据

	/*
	 * 删除数据
	 */
	public Info delete(String key){
		int hashVal=hashCode(key);
		while(arr[hashVal]!=null){
			if(arr[hashVal].getKey().equals(key)){
				Info tmp=arr[hashVal];
				tmp.setName(null); //将name置空
				return tmp;
			}
			hashVal++;
			hashVal%=arr.length;
		}
		return null;
	}

缺陷：占用了别人的位置