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

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 = mPKOUMN0; 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 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.getPrmPKOUMNe());

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();

}

/**

* 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[] 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;

}

}

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。