ArrayList和HashMap如何自己實現(xiàn)實例詳解
更新時間：2016年12月27日 17:32:27 投稿：lqh
這篇文章主要介紹了 ArrayList和HashMap如何自己實現(xiàn)的相關(guān)資料,需要的朋友可以參考下
ArrayList和HashMap
ArrayList的存儲就是一個數(shù)組，
HashMap的存儲是一個數(shù)組加一個鏈表，
以下實現(xiàn)的MyArrayList及MyHashMap，在實際的工作中都是用不上的，最有可能用得到的地方就是面試找工作以及忽悠別人了。工作中雖然用不上，但是并不代表沒有用，它可以幫助我們?nèi)ダ斫馑麄兊膶崿F(xiàn)原理，等實現(xiàn)完后再去仔細查看JDK中的源碼，就會發(fā)現(xiàn)別人實現(xiàn)當(dāng)中那些可供學(xué)習(xí)的地方。
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;
}
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
相關(guān)文章
這篇文章主要介紹了Java List集合排序?qū)崿F(xiàn)方法解析,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-12-12
最近在使用Springboot做項目的時候,遇到了一個循環(huán)依賴的問題,所以下面這篇文章主要給大家介紹了關(guān)于springboot循環(huán)依賴實現(xiàn)以及分析的相關(guān)資料,需要的朋友可以參考下2022-06-06
這篇文章主要介紹了Java中的序列化(Serializable)和反序列化,?JAVA序列化與反序列化就是JAVA對象與一串字節(jié)流之間的相互轉(zhuǎn)換,?我們在程序中創(chuàng)建的JAVA對象只存在于JVM中,需要的朋友可以參考下2023-09-09
在開發(fā)API接口時,配置API接口的超時時間是一項非常重要的任務(wù),SpringBoot中有多種方式可以配置API接口的超時時間,下面小編就為大家介紹一下吧2025-03-03
這篇文章主要介紹了java實現(xiàn)屏幕共享功能的方法,以實例形式分析了屏幕共享功能的客戶端與服務(wù)端的詳細實現(xiàn)方法,是非常具有實用價值的技巧,需要的朋友可以參考下2014-12-12
構(gòu)建springboot自動生成mapper文件和dao接口項目的步驟和配置方法
這篇文章主要介紹了構(gòu)建springboot自動生成mapper文件和dao接口項目的步驟和配置方法，本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-05-05
這篇文章主要介紹了nacos在mac上部署提示找不到或無法加載主類的解決,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-06-06
SpringBoot開發(fā)技巧啟動時配置校驗實現(xiàn)示例
這篇文章主要為大家介紹了SpringBoot開發(fā)在啟動時自動配置校驗的實現(xiàn)示例及原理解析，有需要的朋友可以借鑒參考下希望能夠有所幫助2021-10-10
SpringBoot-Mail工具實現(xiàn)郵箱驗證碼登錄注冊功能
現(xiàn)在許多pc程序都有著使用郵箱驗證碼實現(xiàn)登錄注冊的功能,那么我們應(yīng)該如何完成郵箱驗證碼功能呢,我們可以使用springboot內(nèi)置的springboot-mail再結(jié)合redis來完成這個功能,感興趣的朋友跟隨小編一起看看吧2024-07-07
JavaWeb開發(fā)之Spring+SpringMVC+MyBatis+SpringSecurity+EhCache+JC
這篇文章主要介紹了JavaWeb開發(fā)之Spring+SpringMVC+MyBatis+SpringSecurity+EhCache+JCaptcha 完整Web基礎(chǔ)框架的相關(guān)資料,需要的朋友可以參考下2016-12-12