ArrayList和HashMap
ArrayList的存儲就是一個數組，
HashMap的存儲是一個數組加一個鍊錶，
以下實現的MyArrayList及MyHashMap，在實際的工作中都是用不上的，最有可能用得到的地方就是面試找工作以及忽悠別人了。工作中雖然用不上，但是並不代表沒有用，它可以幫助我們去理解他們的實現原理，等實現完後再去仔細查看JDK中的源碼，就會發現別人實現當中那些可供學習的地方。
MyArrayList
public class MyArrayList<E> { 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(); } /** * @param args */ public static void main(String[] args) { MyArrayList<String> myList = new MyArrayList<String>(); 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<K, V> { //initialization capacity private int capacity = 10; //total entities private int size = 0; private Entity<K, V>[] 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<K, V> newEntity = new Entity<K, V>(key, value); put(newEntity, this.entities, this.capacity); } private void put(Entity<K, V> newEntity, Entity<K, V>[] entities, int capacity) { int index = newEntity.getKey().hashCode() % capacity; Entity<K, V> entity = entities[index]; Entity<K, V> 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<K, V> 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<K, V> 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<K, V> 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(); } /** * Simple re-hash strategy, if the size is bigger than capacity, then do re-hash action */ private void reHash() { if (size >= capacity) { int newCapacity = capacity * 2; @SuppressWarnings("unchecked") Entity<K, V>[] newEntities = new Entity[newCapacity]; for (int i = 0; i < capacity; i++) { Entity<K, V> 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<String, String> map = new MyHashMap<String, String>(); 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<K, V> { private K key; private V value; private Entity<K, V> pre; private Entity<K, V> 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<K, V> getPre() { return pre; } public void setPre(Entity<K, V> pre) { this.pre = pre; } public Entity<K, V> getNext() { return next; } public void setNext(Entity<K, V> next) { this.next = next; } }感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！