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

 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; 
  } 
 
} 

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