一:开始
1.存储数据 put
Map<String,String> map = new HashMap<String,String>();
map.put("1","一");
map.put("2","二");
map.put("3","三");
map.put("4","四");
2.查询数据 get
map.get("1");
map.get("2");
map.get("3");
map.get("4");
二:技术的本质
程序设计 = 数据结构 + 算法
1.数据结构:数组,链表,红黑树(JDK8)
1):数组:采用一段连续的存储单元来存储数据
特点:查询速度快,时间复杂度为O(1)。删除和插入速度慢
2):链表:链表是一种物理存储单元上非连续,非顺序的存储结构
特点:插入,删除时间复杂度为O(1),查找遍历的复杂度为O(N),总结:插入快,查找慢
2.算法:哈希算法
哈希算法:也叫散列,就是把任意长度值(key)通过散列算法变换成固定长度的key(地址)通过这个地址进行访问的数据结构。他通过把关键码值映射到表中一个位置来访问记录。
三:源码
/**
* @author 77916
* @param <K>
* @param <V>
*/
public interface Map<K,V> {
V put(K k,V v);
V get(K k);
int size();
interface Entry<K,V>{
K getKey();
V getValue();
}
}
/**
* 手写实现
* @param <K>
* @param <V>
* @author 77916
*/
public class HashMap<K,V> implements Map<K,V> {
Entry<K,V>[] table = null;
int size = 0;
public HashMap(){
table = new Entry[16];
}
/**
* 1.key进行hash,取模算出index下标
* 2.找到数组对应的节点对象,判断对象是否为空
* 3.如果为空,不会出现冲突,赋值存储即可
* 4.如果不为空,发生哈希冲突,用链表进行存储,返回值
* @param k
* @param v
* @return
*/
@Override
public V put(K k, V v) {
int index = hash(k);
Entry<K, V> entry = table[index];
if(null == entry){
table[index] = new Entry<>(k, v, index, null);
size++;
} else {
table[index] = new Entry<>(k, v, index, entry);
}
return table[index].getValue();
}
private int hash(K k){
int index = k.hashCode() % 16;
return index>=0?index:-index;
}
/**
* 1.key进行hash,取模算出index下标
* 2.找到数组对应的节点对象,判断对象是否为空
* 3.如果为空,直接返回空对象
* 4.如果不为空,用查出来的k和当前k做比较
* 1):如果相等,直接返回数据
* 2):如果不相等,查询next是否为空,为空直接返回
* 3):如果不为空,查询取出来的key和当前的key是否相等,直到相等为止
* @param k
* @return
*/
@Override
public V get(K k) {
int index = hash(k);
Entry<K, V> entry = findValue(table[index],k);
return entry==null?null:entry.getValue();
}
public Entry<K,V> findValue(Entry<K, V> entry,K k){
if (k.equals(entry.getKey()) || k == entry.getKey()){
return entry;
} else {
if( entry.next != null){
return findValue(entry.next, k);
}
}
return null;
}
@Override
public int size() {
return 0;
}
class Entry<K,V> implements Map.Entry<K,V>{
K k;
V v;
int index;
Entry<K,V> next;
public Entry(K k, V v, int index, Entry<K, V> next) {
this.k = k;
this.v = v;
this.index = index;
this.next = next;
}
@Override
public K getKey() {
return k;
}
@Override
public V getValue() {
return v;
}
}
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之家整理,本文链接:https://www.bmabk.com/index.php/post/84149.html