ArrayList和HashMap如何自己实现实例详解

 ArrayList和HashMap

ArrayList的存储就是一个数组，

HashMap的存储是一个数组加一个链表，

以下实现的MyArrayList及MyHashMap，在实际的工作中都是用不上的，最有可能用得到的地方就是面试找工作以及忽悠别人了。工作中虽然用不上，但是并不代表没有用，它可以帮助我们去理解他们的实现原理，等实现完后再去仔细查看JDK中的源码，就会发现别人实现当中那些可供学习的地方。

MyArrayList

public class MyArrayList { 
  private int capacity = 10; 
  private int size = 0; 
  private E[] values = null; 
 
  @SuppressWarnings("unchecked") 
  public MyArrayList() { 
    values = (E[]) new Object[capacity]; 
  } 
 
  @SuppressWarnings("unchecked") 
  public MyArrayList(int capacity) { 
    this.capacity = capacity; 
    values = (E[]) new Object[this.capacity]; 
  } 
 
  public void put(E e) { 
    if (e == null) { 
      throw new RuntimeException("The value should not be null."); 
    } 
    if (size >= capacity) { 
      enlargeCapacity(); 
    } 
    values[size] = e; 
    size++; 
  } 
 
  public E get(int index) { 
    if (index >= size) { 
      throw new RuntimeException("The index:" + index + " is out of band."); 
    } 
    return values[index]; 
  } 
 
  public void remove(int index) { 
    if (index >= size) { 
      throw new RuntimeException("The index:" + index + " is out of band."); 
    } 
    for (int i = index; i < size - 1; i++) { 
      values[i] = values[i + 1]; 
    } 
    values[size - 1] = null; 
    size--; 
  } 
 
  @SuppressWarnings("unchecked") 
  private void enlargeCapacity() { 
    capacity = capacity * 2; 
    E[] tmpValues = (E[]) new Object[capacity]; 
    System.arraycopy(values, 0, tmpValues, 0, size); 
    values = tmpValues; 
  } 
 
  public String toString() { 
    StringBuilder sb = new StringBuilder(); 
    sb.append("["); 
    for (int i = 0; i < size; i++) { 
      sb.append(values[i]).append(","); 
    } 
    if (size > 0) { 
      sb.deleteCharAt(sb.length() - 1); 
    } 
    sb.append("]"); 
    return sb.toString(); 
  } 
 
   
  public static void main(String[] args) { 
    MyArrayList myList = new MyArrayList(); 
    myList.put("1"); 
    myList.put("2"); 
    myList.put("3"); 
    myList.put("4"); 
    myList.put("5"); 
    myList.put("6"); 
    myList.put("7"); 
    myList.put("8"); 
    myList.put("9"); 
    myList.remove(7); 
    System.out.println(myList.toString()); 
  } 
 
} 

MyHashMap

public class MyHashMap { 
  //initialization capacity 
  private int capacity = 10; 
  //total entities 
  private int size = 0; 
  private Entity[] entities = null; 
 
  @SuppressWarnings("unchecked") 
  public MyHashMap() { 
    entities = new Entity[capacity]; 
  } 
 
  public void put(K key, V value) { 
    if (key == null) { 
      throw new RuntimeException("The key is null"); 
    } 
    reHash(); 
    Entity newEntity = new Entity(key, value); 
    put(newEntity, this.entities, this.capacity); 
  } 
 
  private void put(Entity newEntity, Entity[] entities, int capacity) { 
    int index = newEntity.getKey().hashCode() % capacity; 
    Entity entity = entities[index]; 
    Entity firstEntity = entities[index]; 
    if (entity == null) { 
      entities[index] = newEntity; 
      size++; 
    } else { 
      if (newEntity.getKey().equals(entity.getKey())) {//Find the same key for the first entity, if find then replace the old value to new value 
 newEntity.setNext(entity.getNext()); 
 newEntity.setPre(entity.getPre()); 
 if (entity.getNext() != null) { 
   entity.getNext().setPre(newEntity); 
 } 
 entities[index] = newEntity; 
      } else if (entity.getNext() != null) { 
 while (entity.getNext() != null) {//Find the same key for all the next entity, if find then replace the old value to new value 
   entity = entity.getNext(); 
   if (newEntity.getKey().equals(entity.getKey())) { 
     newEntity.setPre(entity.getPre()); 
     newEntity.setNext(entity.getNext()); 
     if (entity.getNext() != null) { 
entity.getNext().setPre(newEntity); 
     } 
     entities[index] = newEntity; 
     return; 
   } 
 } 
 //Cannot find the same key, then insert the new entity at the header 
 newEntity.setNext(firstEntity); 
 newEntity.setPre(firstEntity.getPre()); 
 firstEntity.setPre(newEntity); 
 entities[index] = newEntity; 
 size++; 
      } else { 
 //Cannot find the same key, then put the new entity in head 
 newEntity.setNext(firstEntity); 
 firstEntity.setPre(newEntity); 
 entities[index] = newEntity; 
 size++; 
      } 
    } 
  } 
 
  public V get(K key) { 
    if (key == null) { 
      throw new RuntimeException("The key is null"); 
    } 
    int index = key.hashCode() % capacity; 
    Entity entity = entities[index]; 
    if (entity != null) { 
      if (entity.getKey().equals(key)) { 
 return entity.getValue(); 
      } else { 
 entity = entity.getNext(); 
 while (entity != null) { 
   if (entity.getKey().equals(key)) { 
     return entity.getValue(); 
   } 
   entity = entity.getNext(); 
 } 
      } 
 
    } 
    return null; 
  } 
 
  public void remove(K key) { 
    if (key == null) { 
      throw new RuntimeException("The key is null"); 
    } 
    int index = key.hashCode() % capacity; 
    Entity entity = entities[index]; 
    if (entity != null) { 
      if (entity.getKey().equals(key)) { 
 if (entity.getNext() != null) {//remove the first entity 
   entity.getNext().setPre(entity.getPre()); 
   entities[index] = entity.getNext(); 
   entity = null; 
 } else {//empty this index 
   entities[index] = null; 
 } 
 size--; 
      } else { 
 entity = entity.getNext(); 
 while (entity != null) { 
   if (entity.getKey().equals(key)) { 
     if (entity.getNext() != null) { 
entity.getPre().setNext(entity.getNext()); 
entity.getNext().setPre(entity.getPre()); 
entity = null; 
     } else { 
//release the found entity 
entity.getPre().setNext(null); 
entity = null; 
     } 
     size--; 
     return; 
   } 
   entity = entity.getNext(); 
 } 
      } 
    } 
  } 
 
  public String toString() { 
    StringBuilder sb = new StringBuilder(); 
    for (int i = 0; i < capacity; i++) { 
      sb.append("index=").append(i).append("["); 
      boolean hasEntity = false; 
      Entity entity = entities[i]; 
      if (entity != null) { 
 hasEntity = true; 
      } 
      while (entity != null) { 
 sb.append("[").append(entity.getKey()).append("=").append(entity.getValue()).append("]").append(","); 
 entity = entity.getNext(); 
      } 
      if (hasEntity) { 
 sb.deleteCharAt(sb.length() - 1); 
      } 
      sb.append("]n"); 
    } 
    return sb.toString(); 
  } 
 
   
  private void reHash() { 
    if (size >= capacity) { 
      int newCapacity = capacity * 2; 
      @SuppressWarnings("unchecked") 
      Entity[] newEntities = new Entity[newCapacity]; 
      for (int i = 0; i < capacity; i++) { 
 Entity entity = entities[i]; 
 while (entity != null) { 
   put(entity, newEntities, newCapacity); 
   entity = entity.getNext(); 
 } 
      } 
      this.capacity = newCapacity; 
      this.entities = newEntities; 
    } 
  } 
 
  public static void main(String[] args) { 
    MyHashMap map = new MyHashMap(); 
    map.put("one", "1"); 
    map.put("two", "2"); 
    map.put("three", "3"); 
    map.put("four", "4"); 
    map.put("five", "5"); 
    map.put("six", "6"); 
    map.put("seven", "7"); 
    map.put("eight", "8"); 
    map.put("nine", "9"); 
    map.put("ten", "10"); 
    System.out.println(map.get("one")); 
    System.out.println(map.get("two")); 
    System.out.println(map.get("three")); 
    System.out.println(map.get("four")); 
    System.out.println(map.get("five")); 
    System.out.println(map.get("six")); 
    System.out.println(map.get("seven")); 
    System.out.println(map.get("eight")); 
    System.out.println(map.get("nine")); 
    System.out.println(map.get("ten")); 
    System.out.println(map.toString()); 
 
    map.remove("nine"); 
    map.remove("three"); 
    System.out.println(map.get("one")); 
    System.out.println(map.get("two")); 
    System.out.println(map.get("three")); 
    System.out.println(map.get("four")); 
    System.out.println(map.get("five")); 
    System.out.println(map.get("six")); 
    System.out.println(map.get("seven")); 
    System.out.println(map.get("eight")); 
    System.out.println(map.get("nine")); 
    System.out.println(map.get("ten")); 
    System.out.println(map.toString()); 
  } 
} 
 
class Entity { 
  private K key; 
  private V value; 
  private Entity pre; 
  private Entity next; 
 
  public Entity(K key, V value) { 
    this.key = key; 
    this.value = value; 
  } 
 
  public K getKey() { 
    return key; 
  } 
 
  public void setKey(K key) { 
    this.key = key; 
  } 
 
  public V getValue() { 
    return value; 
  } 
 
  public void setValue(V value) { 
    this.value = value; 
  } 
 
  public Entity getPre() { 
    return pre; 
  } 
 
  public void setPre(Entity pre) { 
    this.pre = pre; 
  } 
 
  public Entity getNext() { 
    return next; 
  } 
 
  public void setNext(Entity next) { 
    this.next = next; 
  } 
 
} 

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！