手动实现arraylist和hashmap

这是第一篇博客，我准备先将最近学习的笔记记录下来，数据结构最基础也最难吧，大佬就别看了。。。

1. Arraylist

    public class LouisArraylist<E> {
    int size;
    Object[] array;
    private static final int MIN_CAPACITY_INCREMENT = 12;
    public LouisArraylist(int capacity){
        if(capacity<0){
        throw new IllegalArgumentException();
    }
        array = new Object[capacity];
    }
   
    public LouisArraylist(){
        array = new Object[0];
    }
   
    public LouisArraylist(Collection<? extends E> collection){
        Object[] a = collection.toArray();
        if(a.getClass()!=Object[].class){
            Object[] newArray = new Object[a.length];
            System.arraycopy(a, 0, newArray, 0, a.length);
            a = newArray;
        }
        array = a;
        size = a.length;
    }
   
    /**
     * 扩容
    * 
    */
    private static int newCapacity(int currentCapacity){
        int increment =   (currentCapacity<MIN_CAPACITY_INCREMENT/2)?MIN_CAPACITY_INCREMENT
                :currentCapacity>>1;
        return currentCapacity+increment;
    }
   
    /**
    * 增加
    */
    public boolean add(E object){
        Object[] a = array;
        int s = size;
        if(s == a.length){
            //需要扩容了
            Object[] newArray = new Object[newCapacity(s)];
            System.arraycopy(a, 0, newArray, 0, s);
            array = a = newArray;
        }
        a[s] = object;
        size = s + 1;
        return true;
    }
   

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size==0;
    }

    /**
    * 查找首次出现元素的下标
    */
    public int indexOf(Object object){
        Object[] a = array;
        int s = size;
        if(object!=null){
            for(int i = 0;i<s;i++){
                if(object.equals(a[i])){
                    return i;
                }
            }
        }else{
            for(int i = 0;i<s;i++){
                if(a[i] == null){
                    return i;
                }
            }
        }
        return -1;
    }

    public int lastIndexOf(Object object){
        Object[] a = array;
        int s = size;
        if(object!=null){
            for(int i = s -1;i >= 0;i--){
                if(object.equals(a[i])){
                    return i;
                }
            }
        }else{
            for(int i = s -1;i >= 0;i--){
                if(a[i] == null){
                    return i;
                }
            }   
        }
        return -1;
    }

    /**
     * 删除某个元素
    */
    public E remove(int index){
        Object [] a = array;
        int s = size;
        if(index >= s){
            throw new IndexOutOfBoundsException();
        }
        E e = (E) a[index];
        System.arraycopy(a, index+1, a, index, --s-index);
        a[s] = null;
        size = s;
        return e;
    }

    /**
     * 删除某个元素
    */
    public boolean remove(Object object){
        Object[] a = array;
        int s = size;
        if (object == null) {
            for (int i = 0; i < size; i++) {
                if (a[i] == null) {
                    remove(i);
                    return true;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (a[i].equals(object)) {
                    remove(i);
                    return true;
                }
            }
        }
        return false;
    }

    public E set(int index,E object){
        Object[] a = array;
        if(index>size){
            throw new IndexOutOfBoundsException();
        }
        E e = (E) a[index];
        a[index] = object;
        return e;
    }

    /**
    * 获取
    */
    public E get(int index){
        Object[] a = array;
        if(index>size){
            throw new IndexOutOfBoundsException();
        }
        E e = (E) a[index];
        return e;
    }
}

代码已经说明的很清楚了，我就不多说什么了，知道底层是数组实现就ok了

2. HashMap

public class LouisHashMap<K, V> {

private int size;
private static final int MINIMUN_CAPACITY = 1 << 2;
private static final int MAXNIMUN_CAPACITY = 1 << 30;
//阈值
private int threshhold;
//用于强制扩容,因为比minimun还小
private static final Map.Entry[] EMPTY_TABLE = new LouisEntry[MINIMUN_CAPACITY >> 1];
private LouisEntry<K, V>[] table; //核心数组
LouisEntry<K, V> entryOrNullKey;  //空键entry

public LouisHashMap() {
    table = (LouisEntry<K, V>[]) EMPTY_TABLE;
    threshhold = -1;
}
public LouisHashMap(int capacity) {
    if (capacity < 0) {
        throw new IllegalArgumentException("capacity :" + capacity);
    } else if (capacity == 0) {
        table = (LouisEntry<K, V>[]) EMPTY_TABLE;
        threshhold = -1;
        return;
    } else if (capacity < MINIMUN_CAPACITY && capacity > 0){
        capacity = MINIMUN_CAPACITY;
    } else if (capacity > MAXNIMUN_CAPACITY) {
        capacity = MAXNIMUN_CAPACITY;
    } else {
        capacity = roundUpToPowerOfTwo(capacity);
    }
    makeTable(capacity);

}

/**
 * 添加
 * @param key
 * @param value
 * @return
 */
public V put(K key, V value) {
    if (key == null) {
        return putValueForNullKey(value);
    }
    int hash = sencondaryHash(key.hashCode());
    LouisEntry<K, V>[] tab = table;
    //将一个很散列的值 位与一个索引大小，会取得0~索引的值
    int index = hash & (table.length - 1);
    //先检查是否存在相同的键
    for (LouisEntry<K, V> e = tab[index]; e != null; e = e.next) {
        //键相同hash值一定相同， hash相同键不一定相同
        if (e.hash == hash && key.equals(e.getKey())) {
            V oldValue = e.getValue();
            e.setValue(value);
            return oldValue;
        }
    }
    //没有覆盖直接插入元素
    if (size++ > threshhold) {
        //创建一个新的容量的数组
        tab = doubleCapacity();
        index = hash & (tab.length - 1);
    }
    addNewEntry(key, value, hash, index);
    return null;
}

private void addNewEntry(K key, V value, int hash, int index) {
    //将新创建的entry加在链表头，一句代码解决两个事情，放头部，放容易查询也容易
    table[index] = new LouisEntry<>(key, value, hash, table[index]);
}

/**
 * get
 * @return
 */
public V get(Object key) {
    if (key == null) {
        LouisEntry<K, V> e = entryOrNullKey;
        return e == null ? null : e.getValue();
    }
    int hash = sencondaryHash(key.hashCode());
    LouisEntry<K, V>[] tab = table;
    int index = hash & (tab.length - 1);
    for (LouisEntry<K, V> entry = tab[index]; entry != null; entry = entry.next) {
        K ekey = entry.key;
        //比较时，先比较对象值是否相等，在比较属性值是否相等，增加效率
       if (ekey == key || (entry.hash == hash && key.equals(ekey))) {
           return entry.value;
       }
    }
    return null;
}
/**
 * 双倍扩容
 * @return
 */
private LouisEntry<K, V>[] doubleCapacity() {
    LouisEntry<K, V>[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXNIMUN_CAPACITY) {
        return oldTable;
    }
    //2的幂次方
    int newCapacity = oldCapacity << 1;
    System.out.println("扩容：" + size);
    LouisEntry<K, V>[] newTable = makeTable(newCapacity);
    if (size == 0) {
        return newTable;
    }
    //开始重新散列
    for (int j = 0; j < oldTable.length; j++) {
        LouisEntry<K, V> e = oldTable[j]; //拿到每个键值对
        if (e == null) {
            continue; //因为每个索引不一定有值，hash
        }
        // 与上面   int index = hash & (table.length - 1);会出现两组数据，一种还在远处，一种去到length的位置
        int highBit = e.hash & oldCapacity;
        LouisEntry<K, V> broken = null;
        //位或 运算最多是原值的两倍，重新一次散列
        newTable[j | highBit] = e;
        for (LouisEntry<K, V> n = e.next; n != null; e = n, n = n.next) {
            //n 为当前遍历的元素， e为前一个
            int nextHighBit = n.hash & oldCapacity;
            if (nextHighBit != highBit) {
                if (broken == null) {
                    int nextNewIndex = j | nextHighBit; //新的索引的位置
                    newTable[nextNewIndex] = n;
                } else {
                    broken.next = n;
                }
                broken = e;
                highBit = nextHighBit;
            }
        }
        if (broken != null) {
            broken.next = null;
        }

    }
    return newTable;
}

/**
 * hashMap键的hash算法
 * @param h
 * @return
 */
private int sencondaryHash(int h) {
    h ^= (h>>>20)^(h>>>12);
    return h^(h>>>7)^(h>>>4);
}

/**
 * 放空键的键值对
 * @param value
 * @return
 */
private V putValueForNullKey(V value) {
    LouisEntry<K, V> entry = entryOrNullKey;
    if (entry == null) {
        addNewEntryForNullKey(value);
        size++;
        return null;
    } else{
        V oldValue = entry.getValue();
        entry.setValue(value);
        return oldValue;
    }
}

private void addNewEntryForNullKey(V value) {
    entryOrNullKey = new LouisEntry<K, V>(null, value, 0, null);
}

/**
 * 根据容量创建核心数组
 * @param capacity
 */
private LouisEntry<K, V>[] makeTable(int capacity) {
    LouisEntry<K, V>[] newTable = new LouisEntry[capacity];
    table = newTable;
    threshhold = (capacity >>> 2) + (capacity >>> 1);
    return newTable;
}

private int roundUpToPowerOfTwo(int i) {
    i--;
    i |= i >>> 1; //  i = i | (i >>> 1) 让所有的位都变成 1 ， 最后在加 1，就可以被2整除
    i |= i >>> 2;
    i |= i >>> 4;
    i |= i >>> 8;
    i |= i >>> 16;
    return i + 1;
}

public int getSize() {
    return size;
}

/**
 * 键值对类
 * @param <K>
 * @param <V>
 */
static class LouisEntry<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;    //此处用final 只赋值一次，因为key是唯一的
    V value;
    LouisEntry<K, V> next;
    public LouisEntry(K key, V value, int hash, LouisEntry<K, V> next) {
        this.key = key;
        this.value = value;
        this.hash = hash;
        this.next = next;
    }
    @Override
    public K getKey() {
        return key;
    }

    @Override
    public V getValue() {
        return value;
    }

    @Override
    public V setValue(V value) {
        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }

    @Override
    public int hashCode() {
        // ^ 异或运算使结果更加散列，相同为0
        return (key == null ? 0 :key.hashCode()) ^ (value == null ? 0 : value.hashCode());
    }
}

}

第一次写博客，注释也很多了，兄弟们自己将就看吧。

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章