Java——容器的简单结构
容器的简单结构
- Collection:接口储存一组不唯一,无序的对象
- List:接口储存一组不唯一,有序(索引顺序)的对象
- Set:接口储存一组唯一,无序的对象
- Map:接口储存一组键值对,提供key到value的映射
key:唯一 无序
value:不唯一 无序
ArrayList:底层是用数组实现的储存。特点:查询效率高,增删效率低,线程不安全,一般使用它。
注意:JavaSE 7以及以后的版本中,构造函数中可以省略泛型类型。ArrayList<String> files = new ArrayList<>();
省略的类型可以从变量的类型中推断的得出。
LinkedList:底层是使用连边实现的。特点:查询效率低,增删效率高,线程不安全
Map:键不能重复,新覆盖旧的
HashMap:底层实现采用了哈希表,这是一种非常重要的数据结构。哈希表的基本机构就是数组+链表。特点:线程不安全,效率高,允许key或value为null
TreeMap:红黑二叉树的典型实现
HashTable:线程安全,效率低,不允许key或value为null
测试Collection个别方法
package Collection_2;
import java.util.ArrayList;
import java.util.Collection;
/*
* 测试Collection接口中的方法
*/
public class TestList {
public static void main(String[] args) {
Collection<String> c = new ArrayList<>();
c.add("阿1");
c.add("阿2"); //添加元素,返回布尔值
System.out.println(c.size()); //获取元素个数,返回整型数值
System.out.println(c.isEmpty()); //是否为空,返回布尔值
System.out.println(c.contains("阿2"));//是否包含元素,返回布尔值
c.remove("阿1"); //删除元素,返回布尔值
System.out.println(c);
Object[] objs = c.toArray(); //返回一个Object类的数组
System.out.println(objs);
}
}
手写ArrayList
package MyArrayList_4;
/*
* 手写ArrayList
*/
public class MyArrayList4<E> {
private Object[] elementData;
private int size;
MyArrayList4() {
elementData = new Object[10];
}
MyArrayList4(int n) {
if (n < 0) {
throw new RuntimeException("不能为负数" + n);
} else if (n == 0) {
elementData = new Object[10];
}
elementData = new Object[n];
}
public void add(E e) {
grow();
elementData[size++] = e;
}
public void add(int index,E e) {
grow();
rangeCheck(index);
System.out.println(elementData.length+"---------"+size);
System.arraycopy(elementData, index,elementData , index+1, size-index);
elementData[index] = e;
size++;
}
private void grow() {
if (size == elementData.length) {
Object[] newObject = new Object[elementData.length + (elementData.length >> 1)];
System.arraycopy(elementData, 0, newObject, 0, elementData.length);
elementData = newObject;
}
}
int size() {
return size;
}
E get(int index) {
rangeCheck(index);
return (E) elementData[index];
}
void set(E e, int index) {
rangeCheck(index);
elementData[index] = e;
}
void rangeCheck(int index) {
if (index < 0 || index > size - 1) {
throw new RuntimeException("数组下标越界" + index);
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
if (size > 0) {
sb.append("[");
for (int i = 0; i < size; i++) {
sb.append(elementData[i] + ",");
}
sb.setCharAt(sb.length() - 1, ']');
}
return sb.toString();
}
void remove(E e) {
for (int i = 0; i < size; i++) {
if (e.equals(elementData[i])) {
remove(i);
}
}
}
boolean isEmpty() {
return size == 0;
}
void remove(int index) {
// a,b,c,d,e,f
// a,b,d,e,f
int number = elementData.length - index - 1;
if (number > 0) {
System.arraycopy(elementData, index + 1, elementData, index, elementData.length - index - 1);
}
elementData[--size] = null;
}
void clear() {
for (int i = 0; i < size; i++) {
elementData[i] = null;
}
size = 0;
}
public static void main(String[] args) {
MyArrayList4<String> ma = new MyArrayList4<>();
for (int i = 0; i < 40; i++) {
ma.add("A" + i);
}
System.out.println(ma.get(10));
ma.set("壹贰叁贰壹", 0);
System.out.println(ma);
ma.remove(10);
System.out.println(ma);
ma.remove("A17");
System.out.println(ma);
System.out.println(ma.size);
System.out.println(ma.isEmpty());
// ma.clear();
ma.add(36, "测试ssssss");
System.out.println(ma);
}
}
手写LinkedList
package MyLinkedList_5;
/*
* 手写LinkedList
*/
public class MyLinkedList5 <E>{
private Node first; // 第一个节点
private Node last; // 最后的节点
private int size;
// a,b,c,d
void add(E e) {
Node node = new Node(e);
if (first == null) {
first = node;
last = node;
} else {
node.previous = last;
node.next = null;
last.next = node;
last = node;
}
size++;
}
void add(int index,E e) {
if (index < 0 || index > size - 1) {
throw new RuntimeException("索引越界:" + index);
}
Node newNode = new Node(e);
Node temp = getNode(index);
if(temp!=null) {
Node up = temp.previous;
if(up!=null) {
up.next = newNode;
newNode.previous = up;
newNode.next = temp;
temp.previous = newNode;
}else {
newNode.next = temp;
temp.previous = newNode;
first = newNode;
}
}
size++;
}
E get(int index) {
if (index < 0 || index > size - 1) {
throw new RuntimeException("索引越界:" + index);
}
Node temp = getNode(index);
return temp != null ? (E)temp.element : null;
}
void remove(int index) {
Node temp = getNode(index);
Node up = temp.previous;
Node domn = temp.next;
if(up!=null) {
up.next = domn;
}else {
first = domn;
}
if(domn!=null) {
domn.previous = up;
}else {
last=up;
}
size--;
}
Node getNode(int index) {
Node temp = first;
if (index < (size >> 1)) {
for (int i = 0; i < index; i++) {
temp = temp.next;
}
} else {
temp = last;
for (int i = size - 1; i > index; i--) {
temp = temp.previous;
}
}
return temp;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node temp = first;
sb.append("[");
while (temp != null) {
sb.append(temp.element + ",");
temp = temp.next;
}
sb.setCharAt(sb.length() - 1, ']');
return sb.toString();
}
public static void main(String[] args) {
MyLinkedList5<String> list = new MyLinkedList5<>();
list.add("a");
list.add("b");
list.add("d");
list.add("e");
list.add("f");
list.add("g");
System.out.println(list);
System.out.println(list.get(5));
list.remove(0);
System.out.println(list);
list.remove(2);
System.out.println(list);
list.remove(3);
System.out.println(list);
list.add(2,"sss");
System.out.println(list);
System.out.println(list.get(0));
}
}
手写HashMap
package MyHashMap_7;
public class Node1 <K,V>{
int hash;
K key;
V value;
Node1 next;
}
package MyHashMap_7;
/*
* 手写HashMap
*/
public class MyHashMap5 <K,V>{
Node[] table; //位桶数组
int size;
public MyHashMap5() {
table = new Node[16]; //位桶数组长度
}
public void put(K key,V value) {
Node newNode = new Node(); //新节点
newNode.hash = myHash(key.hashCode(),table.length); //获得哈希值
// System.out.println(newNode.hash);
newNode.key = key;
newNode.value = value;
boolean ss = false;
Node temp = table[newNode.hash]; //指向哈希值对应的位桶数组
Node last = null;
if(temp==null) {
table[newNode.hash] = newNode;
}else {
while(temp!=null) {
if(temp.key.equals(key)) {
ss = true;
temp.value = value;
break;
}else {
last = temp;
temp = temp.next;
}
}
if(!ss) {
last.next = newNode;
}
}
}
V get(K key) {
int hash = myHash(key.hashCode(),table.length);
// System.out.println(key.hashCode());
V value = null;
// System.out.println(table[hash]);
if(table[hash]!=null) {
Node temp = table[hash];
while(temp!=null) {
if((temp.key).equals(key)) {
value = (V) temp.value;
break;
}else {
temp = temp.next;
}
}
}
return value;
}
public int myHash(int v,int length) {
// System.out.println(v&(length-1));
return v&(length-1); //通过位运算计算出散列哈希值
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("{");
for(int i=0;i<table.length;i++) {
Node temp = table[i];
while(temp!=null) {
sb.append(temp.key+":"+temp.value+",");
temp = temp.next;
}
}
sb.setCharAt(sb.length()-1, '}');
return sb.toString();
}
public static void main(String[] args) {
MyHashMap5<Integer,String> myMap = new MyHashMap5<>();
myMap.put(10, "a");
myMap.put(20, "b");
myMap.put(30, "c");
System.out.println(myMap);
System.out.println(myMap.get(20));
System.out.println(myMap.get(30));
}
}
手写HashSet
package MyHashSet_10;
import java.util.HashMap;
/*
* 手写HashSet
*/
public class MyHashSet {
HashMap map;
private final Object PRESENT = new Object();
public MyHashSet() {
map = new HashMap();
}
public int size() {
return map.size();
}
public void add(Object key) {
map.put(key, PRESENT);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
for (Object key : map.keySet()) {
sb.append(key + ",");
}
sb.setCharAt(sb.length() - 1, ']');
return sb.toString();
}
public static void main(String[] args) {
MyHashSet my = new MyHashSet();
my.add("a");
my.add("b");
my.add("c");
System.out.println(my);
}
}