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

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

# ArrayList和HashMap  # 如何自己实现  # ArrayList  # HashMap  # 浅析java中ArrayList与Vector的区别以及HashMap与Hashtable的区别  # 深入探讨JavaScript的最基本部分之执行上下文  # 谈谈JavaScript中super(props)的重要性  # JavaScript常用工具方法封装  # Java多线程实战之交叉打印的两种方法  # Java多线程实战之单例模式与多线程的实例详解  # JavaTCP上传文本文件代码  # Java五子棋AI实现代码  # Javascript迭代、递推、穷举、递归常用算法实例讲解  # ArrayList及HashMap的扩容规则讲解  # 不上  # 都是  # 是一个  # 他们的  # 就会  # 希望能  # 人了  # 它可以  # 可供  # 再去  # 并不代表  # 谢谢大家  # 完后  # 链表  # 在实际  # 有可能用  # Object  # void  # throw  # put 

相关文章： 如何通过网站建站时间优化SEO与用户体验？  极客网站有哪些,DoNews、36氪、爱范儿、虎嗅、雷锋网、极客公园这些互联网媒体网站有什么差异？  东莞市网站制作公司有哪些,东莞找工作用什么网站好？  如何快速上传自定义模板至建站之星？  定制建站方案优化指南：企业官网开发与建站费用解析  如何在万网ECS上快速搭建专属网站？  关于BootStrap modal 在IOS9中不能弹出的解决方法(IOS 9 bootstrap modal ios 9 noticework)  建站之星官网登录失败？如何快速解决？  微网站制作教程,我微信里的网站怎么才能复制到浏览器里？  宝塔建站后网页无法访问如何解决？  如何挑选高效建站主机与优质域名？  名字制作网站免费,所有小说网站的名字？  高配服务器限时抢购：企业级配置与回收服务一站式优惠方案  建站VPS配置与SEO优化指南：关键词排名提升策略  如何高效配置IIS服务器搭建网站？  如何用花生壳三步快速搭建专属网站？  建站之星免费版是否永久可用？  建站之星IIS配置教程：代码生成技巧与站点搭建指南  高防服务器租用如何选择配置与防御等级？  如何在Golang中引入测试模块_Golang测试包导入与使用实践  怎么制作一个起泡网,水泡粪全漏粪育肥舍冬季氨气超过25ppm，可以有哪些措施降低舍内氨气水平？  陕西网站制作公司有哪些,陕西凌云电器有限公司官网？  湖州网站制作公司有哪些,浙江中蓝新能源公司官网？  实例解析angularjs的filter过滤器  如何制作新型网站程序文件,新型止水鱼鳞网要拆除吗？  如何选择适配移动端的WAP自助建站平台？  C#如何在一个XML文件中查找并替换文本内容  网站制作需要会哪些技术,建立一个网站要花费多少？  已有域名能否直接搭建网站？  如何在沈阳梯子盘古建站优化SEO排名与功能模块？  如何快速生成可下载的建站源码工具？  建站之星如何助力企业快速打造五合一网站？  实现点击下箭头变上箭头来回切换的两种方法【推荐】  上海网站制作网页,上海本地的生活网站有哪些？最好包括生活的各个方面的？  Python路径拼接规范_跨平台处理说明【指导】  宿州网站制作公司兴策,安徽省低保查询网站？  如何注册花生壳免费域名并搭建个人网站？  官网建站费用明细查询_企业建站套餐价格及收费标准指南  如何在阿里云虚拟服务器快速搭建网站？  专业网站制作服务公司,有哪些网站可以免费发布招聘信息？  洛阳网站制作公司有哪些,洛阳的招聘网站都有哪些？  深圳网站制作的公司有哪些,dido官方网站？  浙江网站制作公司有哪些,浙江栢塑信息技术有限公司定制网站做的怎么样？  北京网页设计制作网站有哪些,继续教育自动播放怎么设置？  新网站制作渠道有哪些,跪求一个无线渠道比较强的小说网站，我要发表小说？  官网自助建站系统：SEO优化+多语言支持，快速搭建专业网站  如何在IIS7上新建站点并设置安全权限？  零基础网站服务器架设实战：轻量应用与域名解析配置指南  单页制作网站有哪些,朋友给我发了一个单页网站，我应该怎么修改才能把他变成自己的呢，请求高手指点迷津？  官网网站制作腾讯审核要多久,联想路由器newifi官网