一、快速使用
首先我们先来了解一下HashMap的基本使用:
public static void mian(String[] args){
Map<String,String> map = new HashMap<>();
map.put("key","value");
System.out.println(map.get("key"));
}
二、技术的本质
hashmap的数据结构是由:数组、链表组成的;
1、数组:采用一段连续的存储单元来存储数据。
特点:数组查询快,插入慢;
2、链表:链表是一种物理存储单元上非连续、非顺序的存储结构
特点:插入、删除的时间复杂度为O(1),查询遍历时间复杂度为O(n)。插入快,查找慢。
让我们顺便来复习一下链表的基本使用:
public class Node {
public Node next;
private Object data;
public Node(Object data){
this.data = data;
}
public static void main(String[] args) {
Node head = new Node("one");
head.next = new Node("two");
head.next.next = new Node("three");
System.out.println(head.data);
System.out.println(head.next.data);
System.out.println(head.next.next.data);
}
}
顺便提一下,在面试中,我们可能会遇到面试官提这样的一个问题,ArrayList与LinkedList的区别:
(1)如果我们查询的数据经常用来查询,但是不需要用来修改数据,建议可以使用ArrayList,因为ArrayList底层用的是数组,数组查询是非常快的。
(2)如果对数据需要进行频繁的修改,我建议使用LinkedList,因为LinkedList底层使用的是链表结构,删除,插入,修改数据是非常快的。
hashmap采用的算法:哈希算法
哈希算法(散列):就是把任意长度值(key)通过散列算法变换成固定长度的key(地址)通过这个地址进行访问的数据结构。它通过把关键码值映射到表中一个。位置来访记录,以加快查找的速度。
hashcode:通过字符串算出它的ascii码,进行mod(取模),算出哈希表的下标。
使用哈希算法会造成哈希冲突,因此采用链表的方式可以有效的解决哈希碰撞的问题。
三、代码实现
以下实现为jdk1.7的代码复现:
定义一个Map的接口
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();
}
}
对Map接口进行实现
public class HashMap<K,V> implements Map<K,V> {
Entry<K,V>[] table = null;
int size = 0;
public HashMap(){
table = new Entry[16];
}
@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);
}
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;
}
@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 size;
}
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;
}
}
}
进行验证测试
public static void main(String[] args) {
HashMap<Object, Object> map = new HashMap<>();
map.put("one","one");
map.put("two","two");
System.out.println(map.get("one"));
System.out.println(map.get("two"));
}
在jdk1.8之后,hashmap采用红黑树加数组的形式,和链表加数组的形式,当大于8的时候采用红黑树在数据,小于8时候采用链表加数组,这一方法很好的解决了链表查询数据慢的问题。由于红黑树在新增数据慢,所以采用设置阈值的方式。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)