源代码：https://gitee.com/AgentXiao/Collection
一、HashMap的底层实现（线程不安全，效率高）
HashMap的存储方式是键（key）值（value）对。
二、自己实现一个简单的HashMap
（1）键值对类
package pri.xiaowd.demo03;
/**
* @ClassName Entry
* @Description 键值对
* @Author xwd
* @Date 2018/10/7 15:43
*/
public class Entry {
private Object key;
private Object value;
public Entry() {
}
public Entry(Object key, Object value) {
this.key = key;
this.value = value;
}
public Object getKey() {
return key;
}
public void setKey(Object key) {
this.key = key;
}
public Object getValue() {
return value;
}
public void setValue(Object value) {
this.value = value;
}
}
（2）以一个数组的方式存储键值对，不考虑数组扩容的问题（直接初始化一个大容量的数组）
private Entry[] entry = new Entry[1024];
private int size;//键值对的个数
（3）size()
add(Object key,Object value)
get(Object key)
remove(Object obj)
/**
* @MethodName size
* @Descrition 获得键值对的个数
* @Param []
* @return int
*/
public int size(){
return size;
}
/**
* @MethodName put
* @Descrition 添加键值对
* @Param [obj, value]
* @return void
*/
public void put(Object obj,Object value){
Entry e = new Entry(obj,value);//新建一个键值对
entry[size++] = e;
}
/**
* @MethodName get
* @Descrition 根据键查找值
* @Param [key]
* @return java.lang.Object
*/
public Object get(Object key){
for(int i=0;i<size;i++){
if(entry[i].getKey().equals(key)){
return entry[i].getValue();
}
}
return null;
}
/**
* @MethodName remove
* @Descrition 移除键值对
* @Param [key]
* @return void
*/
public void remove(Object key){
for(int i=0;i<size;i++){
if(entry[i].getKey().equals(key)){
int numMoved = size-1-i; //如果需要移除的是最后一个，则不需要进行拷贝搬移，而是直接将最后一个赋值null
if(numMoved > 0){
System.arraycopy(entry,i+1,entry,i,numMoved);
}
size--;
entry[size] = null;
}
}
}
（4）containKey(Object key)
containValue(Object value)
/**
* @MethodName containsKey
* @Descrition 判断是否存在key
* @Param [key]
* @return boolean
*/
public boolean containsKey(Object key){
for(int i=0;i<size;i++){
if(entry[i].getKey().equals(key)){
return true;
}
}
return false;
}
/**
* @MethodName containValue
* @Descrition 判断似乎否存在value
* @Param [value]
* @return boolean
*/
public boolean containValue(Object value){
for(int i=0;i<size;i++){
if(entry[i].getValue().equals(value)){
return true;
}
}
return false;
}
（5）考虑到键不能重复，对put方法做一下改进
/**
* @MethodName put
* @Descrition 添加键值对
* @Param [obj, value]
* @return void
*/
public void put(Object key,Object value){
Entry e = new Entry(key,value);//新建一个键值对
//判断是否已经存在key，如果有的话直接覆盖
for(int i=0;i<size;i++){
if(entry[i].getKey().equals(key)){
entry[i].setValue(value);
return;
}
}
entry[size++] = e;
}
（6）这种写法效率低，因为如果有很多键值对，每次都要一个一个遍历。
三、升级版的HashMap（通过hashCode精准定位在数组的那个位置，如果位置重复使用链表进行存储）
数组+链表
private LinkedList[] entry = new LinkedList[1024];//Map的底层实现：数组+链表
private int size;//键值对的个数
（1）put和get方法
/**
* @MethodName put
* @Descrition 添加键值对
* @Param [obj, value]
* @return void
*/
public void put(Object key,Object value){
Entry entry = new Entry(key,value);
int hash = key.hashCode()%1024;//取余数，是0-1023之间的数值,可以定位数组的位置
if(entryLinked[hash] == null){ //如果该位置还没有链表对象,新建一个并添加
LinkedList linkedList = new LinkedList();
entryLinked[hash] = linkedList;
linkedList.add(entry);
}else{ //如果该位置已经有链表对象,直接添加,但是要先判断是否重复
LinkedList list = entryLinked[hash];
for(int i=0;i<list.size();i++){
Entry e = (Entry) list.get(i);
if(e.getKey().equals(key)){
e.setValue(value);
return;
}
}
entryLinked[hash].add(entry);
}
}
/**
* @MethodName get
* @Descrition 根据key获取value
* @Param [key]
* @return java.lang.Object
*/
public Object get(Object key){
int hash = key.hashCode()%1024;
if(entryLinked[hash] != null){
LinkedList list = entryLinked[hash];
for(int i=0;i<list.size();i++){
Entry e = (Entry) list.get(i);
if(e.getKey().equals(key)){
return e.getValue();
}
}
}
return null;
}
（2）equals和hashCode
Java中规定，如果两个对象调用equals返回true，他们的hashCode是相等的。equals方法默认比较两者是否使用一个对象，在String中是重写过的，可以比较两者的内容是否相同。
注意：hashCode也可能是负数，做以下的改进
int hashNum = key.hashCode();
int hash = hashNum > 0 ? hashNum:-hashNum;
hash = hash%1024;//取余数，是0-1023之间的数值,可以定位数组的位置
四、HashSet 无序不可重复 通过HashMap实现
1、add(Object key)：将key添加到HashMap的key中
JDK源代码如下：
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
set的不可重复是利用了map的键不可重复特性
自己实现的代码如下：
/**
* @MethodName add
* @Descrition 添加内容
* @Param [obj]
* @return void
*/
public void add(Object obj){
map.put(obj,PRESENT);//set的不可重复是利用了map的键不可重复特性
}
2、自己实现HashSet
/**
* @ClassName MyHashSet
* @Description 自己实现HashSet
* @Author xwd
* @Date 2018/10/7 17:53
*/
public class MyHashSet {
private HashMap map;
private static final Object PRESENT = new Object();
public MyHashSet() {
map = new HashMap();
}
/**
* @MethodName size
* @Descrition 得到元素个数，直接返回map的size()，
* @Param []
* @return int
*/
public int size(){
return map.size();
}
/**
* @MethodName add
* @Descrition 添加内容
* @Param [obj]
* @return void
*/
public void add(Object obj){
map.put(obj,PRESENT);//set的不可重复是利用了map的键不可重复特性
}
/**
* @MethodName remove
* @Descrition 移除内容
* @Param [obj]
* @return void
*/
public void remove(Object obj){
map.remove(obj);
}
}
五、总结
ArrayList：有序可重复
LinkedList：无序可重复
HashMap：有序不可重复
HashSet：无序不可重复
