hashmap.png
贴代码了！
- Map.java
package com.cqu.practice1;
public interface Map<K, V> {
//向HashMap中插入值
public V put(K k,V v);
//根据Key获取HashMap中的值
public V get(K k);
//获取集合中的元素个数
public int size();
//获取集合中键值对的对象
interface Entry<K,V>{
K getKey();
V getValue();
V setValue(V v);
}
}
- HashMap.java
package com.cqu.practice1;
public class HashMap<K,V> implements Map<K, V> {
//数据存储结构=》 数组加链表
Node<K,V>[] array=null;
//数组/hash桶的初始长度
private static int defaultLength=16;
//加载因子/扩容因子
private static double factor=0.75;
//集合中元素的个数
private int size;
//put元素方法
@Override
public V put(K k, V v) {
//1、懒加载机制，使用的时候进行分配
if(array==null) {
array=new Node[defaultLength];
}
//2、通过hash算法，计算出具体插入的位置
int index=Position(k, defaultLength);
//判断是否需要扩容
if(size>defaultLength*factor) {
resize();
}
//加入要放入的元素
Node<K,V> node=array[index];
if(node==null) {
array[index]=new Node<K,V>(k,v,null);
size++;
}else {
if(k.equals(node.getKey())||k==node.getKey()) {
return node.setValue(v);
}else {
array[index]=new Node<K,V>(k,v,node);
size++;
}
}
return null;
}
//对这个HashMap结构进行扩容操作
private void resize() {
//进行翻倍扩容
Node<K,V>[] temp=new Node[defaultLength<<1];
//reHash
Node<K,V> node=null;
for(int i=0;i<array.length;i++) {
node=array[i];
while(node!=null) {
//重新散列 着重理解一下这里！
int index=Position(node.getKey(), temp.length);
Node<K,V> next=node.next;
node.next=temp[index];
temp[index]=node;
node=next;
}
}
//替换掉旧的array
array=temp;
defaultLength=temp.length;
temp=null;
}
//计算放入元素在hash桶当中的位置,先计算hashCode,再对桶容量作取模运算
private int Position(K k,int Length) {
int code=k.hashCode();
//取模算法
return code%(Length-1);
}
@Override
public V get(K k) {
if(array!=null) {
int index=Position(k, defaultLength);
//获取对应的hash桶节点
Node<K,V> node=array[index];
//遍历链表
while(node!=null) {
if(node.getKey()==k) {
return node.getValue();
}else {
node=node.next;
}
}
}
return null;
}
@Override
public int size() {
return 0;
}
//实现HashMap当中的Entry结构，其实就是Key+Value+指向下一个节点的指针
static class Node<K,V> implements Map.Entry<K, V>{
K key;
V value;
Node<K,V> next;
public Node(K key,V value,Node<K,V> next) {
this.key=key;
this.value=value;
this.next=next;
}
@Override
public K getKey() {
return this.key;
}
@Override
public V getValue() {
return this.value;
}
@Override
public V setValue(V v) {
V oldValue=this.value;
this.value=v;
return oldValue;
}
}
//调试打印函数
public void print() {
System.out.println("***************");
if (array != null) {
Node<K, V> node = null;
for (int i = 0; i < array.length; i++) {
node = array[i];
System.out.print("下标【" + i + "】");
while (node != null) {
System.out.print("[" + node.getKey() + ":" + node.getValue() + "]");
if (node != null)
node = node.next;
else
node = null;
}
System.out.println();
}
}
}
public static void main(String[] args) {
HashMap<String,String> map=new HashMap<>();
for(int i=1;i<50;i++) {
map.put("0"+i+"号", "0"+i);
}
map.print();
System.out.println("--->" + map.get("01号"));
System.out.println("029号".hashCode());
}
}
- 测试输出结果
***************
下标【0】
下标【1】
下标【2】
下标【3】
下标【4】
下标【5】
下标【6】[039号:039][018号:018]
下标【7】[037号:037][016号:016]
下标【8】[035号:035][014号:014]
下标【9】[033号:033][012号:012]
下标【10】[031号:031][010号:010]
下标【11】
下标【12】[026号:026]
下标【13】
下标【14】
下标【15】
下标【16】
下标【17】
下标【18】
下标【19】
下标【20】
下标【21】
下标【22】[049号:049][028号:028]
下标【23】[047号:047]
下标【24】[045号:045][024号:024]
下标【25】[043号:043][022号:022]
下标【26】[041号:041][020号:020]
下标【27】[09号:09]
下标【28】[07号:07]
下标【29】[05号:05]
下标【30】[03号:03]
下标【31】[01号:01]
下标【32】
下标【33】
下标【34】
下标【35】
下标【36】
下标【37】[019号:019]
下标【38】[038号:038][017号:017]
下标【39】[036号:036][015号:015]
下标【40】[034号:034][013号:013]
下标【41】[032号:032][011号:011]
下标【42】[030号:030]
下标【43】
下标【44】
下标【45】
下标【46】
下标【47】
下标【48】
下标【49】
下标【50】
下标【51】
下标【52】
下标【53】[029号:029]
下标【54】[048号:048][027号:027]
下标【55】[046号:046][025号:025]
下标【56】[044号:044][023号:023]
下标【57】[042号:042][021号:021]
下标【58】[040号:040]
下标【59】[08号:08]
下标【60】[06号:06]
下标【61】[04号:04]
下标【62】[02号:02]
下标【63】
--->null
1501280//这是验证hashcode用的
网友评论