JAVA--哈希表
哈希表是一种以键值key存储数据value的结构，以key作为标识值存储value值；只要输入待查找的key，即可获取其对应的value值
思路很简单，所有的key的hashcode值都是整数，那么就可以使用一个简单的数组来实现：将key作为索引，存储的数据就是value，这样就可以达到通过key快速访问任意value值的目的哈希表提供了一组key-value键值对的存取操作，其中存储的每个数据对象都有一个相应的key，键key决定了值value存储的位置
键必须唯一，不允许重复，每个key只能映射一个value
hash冲突，由于映射的范围限制，key取值的可能性大于映射范围，出现两个不同的key映射到同一个位置
Map接口
定义map对象时建议指定key和value对应的类型，key和value要求必须时复杂类型，不能采用int之类的简单类型，map接口中有一个内部接口Entry，每个Entry对象用于封装一对key/value，value允许修改，但是key不允许修改。另外Entry接口中通过静态方法提供了一组比较器的默认实现，用于规范其中存放数据的规则。map中所有存储的数据都将封装为Entry对象，一个key/value对对应一个Entry对象
public interface Map<K,V>{
}
interface Entry<K, V> {
K getKey();
V getValue();
V setValue(V value);
}
Map接口中的常见方法
Object put(Object key, Object value)用于存储一个键值对，如果出现key值冲突，则后盖前；允许
key和value为null，但是key值只能有一个null，value没有null的个数限制
int size()获取集合中元素Entry的个数
Object remove(Object key)根据key值移除对应的key-value键值对，并且返回删除的value值
Object get(Object key)按照key值获取对应的value值，如果key值不存在则返回null
boolean containsKey(Object key)判断map中是否存在某个特定的key值
boolean containsValue(Object value)判断map中是否存在某个特定的value值
void clear() 清空当前map中的所有元素
Set keySet()返回所有key所组成的Set集合，然后就可以通过key值获取对应的 value值
Collection values()获取所有value值所构成的Collection集合
Set entrySet()返回map中所存储的所有entry对象，一个 entry中保存一个key/value键值对
forEach和lambda表达式实现map输出
遍历访问
依赖key值进行遍历
Set<String> keys=map.keySet();//获取map中所有的key所组成的Set集合
Iterator<String> it=keys.iterator();
while(it.hasNext()){
String key=it.next();
Integer value=map.get(key); //根据key获取key所对应的value值
}
直接遍历所有的value值
//没有直接提供方法根据value获取对应的key，因为value值 没有唯一性的约束
Collection<Integer> values=map.values();
values.forEach(System.out::println);
获取所有的entry，存储在map中的键值对都是封装为Entry对象，一个key-value对对应一个entry对象
Set<Entry<String,Integer>> sets=map.entrySet();
for(Entry<String,Integer> tmp:sets){
String key=tmp.getKey(); //获取一个key-value中的key值
Integer value=tmp.getValue(); //获取一个key-value中的value值
}
Map的实现类
常见的实现类HashMap、TreeMap、LinkedHashMap、Hashtable等
HashMap
HashMap是Map接口的实现类
如果不指定泛型，则默认key-value的类型都是Object
class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>,Cloneable, Serializable{
@Override
public Set<Entry<K, V>> entrySet() {
// TODO Auto-generated method stub
return null;
}
}
静态内部类Node用于实现了Entry接口，HashMap中存储的key-value对的数据被封装为Node对象，其中key就是存放的键值，用于决定具体的存放位置【桶的位置】；value就是具体存放的数据；hash就是当前Node对象的hash值缓存；next用于指向下一个Node节点【单向链表】
static class Node<K,V> implements Map.Entry<K,V> {
int hash;
K key;
V value;
Node<K,V> next;
@Override
public K getKey() {
// TODO Auto-generated method stub
return null;
}
@Override
public V getValue() {
// TODO Auto-generated method stub
return null;
}
@Override
public V setValue(V value) {
// TODO Auto-generated method stub
return null;
}
}
构造器
无参构造器
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
构建一个空的HashMap，默认使用初始化容积值16，默认负载因子值为0.75。当前Map集合中允许存放的元素个数为【初始化容积值*负载因子】,16*0.75=12,当集合中存放的key-value个数超过12时，会自动进行扩容处理
HashMap的存储结构
具体存放数据采用的是Node[]数组，每个数组中的元素称为一个桶bucket，一个桶对应一个hash映射的值，例如0、1等，可能会出现不同的key，但是映射位置相同，例如16和32映射的位置都是0【hash%16】，所以这里采用单向链表存储hash映射值相同的所有数据。为了避免一个单向链过长的问题，所以JDK1.8引入了红黑树，当一个链表上的元素个数大于8时，会自动将链表(O(n))转换为红黑树，以提高检索效率(O(logN));当删除节点使某个红黑树上的节点个数小于阈值(6)时会自动将红黑树转换为单向链表