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

}

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

(0)

相关推荐

  • JAVA LinkedList和ArrayList的使用及性能分析

    第1部分 List概括List的框架图List 是一个接口,它继承于Collection的接口.它代表着有序的队列.AbstractList 是一个抽象类,它继承于AbstractCollection.AbstractList实现List接口中除size().get(int location)之外的函数.AbstractSequentialList 是一个抽象类,它继承于AbstractList.AbstractSequentialList 实现了"链表中,根据index索引值操作链表的全部函数

  • 浅析java中ArrayList与Vector的区别以及HashMap与Hashtable的区别

    就ArrayList与Vector主要从二方面来说.一.同步性:Vector是线程安全的,也就是说是同步的,而ArrayList是线程序不安全的,不是同步的 二.数据增长:当需要增长时,Vector默认增长为原来一培,而ArrayList却是原来的一半 就HashMap与HashTable主要从三方面来说.一.历史原因:Hashtable是基于陈旧的Dictionary类的,HashMap是Java 1.2引进的Map接口的一个实现 二.同步性:Hashtable是线程安全的,也就是说是同步的,

  • JAVA ArrayList详细介绍(示例)

    第1部分 ArrayList介绍ArrayList 是一个数组队列,相当于 动态数组.与Java中的数组相比,它的容量能动态增长.它继承于AbstractList,实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口.ArrayList 继承了AbstractList,实现了List.它是一个数组队列,提供了相关的添加.删除.修改.遍历等功能.ArrayList 实现了RandmoAccess接口,即提供了随机访问功能.Randmo

  • Java中Vector与ArrayList的区别详解

    首先看这两类都实现List接口,而List接口一共有三个实现类,分别是ArrayList.Vector和LinkedList.List用于存放多个元素,能够维护元素的次序,并且允许元素的重复.3个具体实现类的相关区别如下:1.ArrayList是最常用的List实现类,内部是通过数组实现的,它允许对元素进行快速随机访问.数组的缺点是每个元素之间不能有间隔,当数组大小不满足时需要增加存储能力,就要讲已经有数组的数据复制到新的存储空间中.当从ArrayList的中间位置插入或者删除元素时,需要对数组

  • 解析C#中[],List,Array,ArrayList的区别及应用

    [] 是针对特定类型.固定长度的. List 是针对特定类型.任意长度的. Array 是针对任意类型.固定长度的. ArrayList 是针对任意类型.任意长度的. Array 和 ArrayList 是通过存储 object 实现任意类型的,所以使用时要转换. 应用示例 复制代码 代码如下: using System; using System.Collections.Generic; using System.Linq; using System.Web; using System.Web

  • java使用listIterator逆序arraylist示例分享

    思路分析:要逆序遍历某个列表,首先要获得一个ListIterator对象,利用for()循环,以ListIterator类的hasNext()方法作为判断条件,通过循环执行ListIterator类的next()方法将游标定位到列表结尾,然后在另一个for循环中,以ListIterator类的hasPrevious()方法作为判断条件,通过ListIterator类的previous()方法逆序输出列表中的元素. 代码如下: 复制代码 代码如下: import java.util.ArrayLi

  • Java中ArrayList类的使用方法

    Java中ArrayList类的用法 1.什么是ArrayList ArrayList就是传说中的动态数组,用MSDN中的说法,就是Array的复杂版本,它提供了如下一些好处: 动态的增加和减少元素 实现了ICollection和IList接口 灵活的设置数组的大小 2.如何使用ArrayList 最简单的例子: ArrayList List = new ArrayList(); for( int i=0;i <10;i++ ) //给数组增加10个Int元素 List.Add(i); //..

  • java中ArrayList 、LinkList的区别分析

    1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构.      2.对于随机访问get和set,ArrayList优于LinkedList,因为ArrayList可以随机定位,而LinkedList要移动指针一步一步的移动到节点处.(参考数组与链表来思考)     3.对于新增和删除操作add和remove,LinedList比较占优势,只需要对指针进行修改即可,而ArrayList要移动数据来填补被删除的对象的空间. ArrayList和LinkedL

  • java的arraylist排序示例(arraylist用法)

    写了一个java数组排序示例,这里分享给大家共同学习 复制代码 代码如下: package com.yonyou.test;import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.List;public class Test { public static void main(String[] args) {  Student zlj = new St

  • C#中Array与ArrayList用法及转换的方法

    ArrayList与Array的区别概述 ArrayList 是数组的复杂版本.ArrayList 类提供在大多数 Collections 类中提供但不在 Array 类中提供的一些功能.例如: Array 的容量是固定的,而 ArrayList 的容量是根据需要自动扩展的.如果更改了 ArrayList.Capacity 属性的值,则自动进行内存重新分配和元素复制. ArrayList 提供添加.插入或移除某一范围元素的方法.在 Array 中,您只能一次获取或设置一个元素的值. 使用 Syn

随机推荐