章节17 容器深入研究 - 《Thinking In Java 中文版》

ArrayList Api调用：
LinkedList Api的调用
填充容器
可选操作
Set和存储顺序
- SortedSet
队列
- 优先级队列
- 双向队列
理解Map
- 性能
- SortedMap
散列和散列码
- 为速度而散列
- 覆盖hashcode（）

ArrayList Api调用：

public class ArrayListDemo {
    public static void main(String[] args) {
        final ArrayList<String> list = new ArrayList<>();
        list.add("wgx");
        list.add("ssn");
        list.add("wh");
        list.add("wbt");//添加数据
        System.out.println(list);
        System.out.println(list.get(2));//读取指定下标的数据
        list.add(1,"zmy");//指定下下标加数据，剩余下边向后移
        System.out.println(list);
        System.out.println(list.isEmpty());//判断是否为空
        final ArrayList<String> list1 = new ArrayList<>();
        list1.add("wgx");
        list1.add("wbt");
        System.out.println(list.containsAll(list1));//是否包含后面的集合中的元素和顺序无关
        System.out.println(list.contains("ssn"));//是否包含后面的元素
        System.out.println(list.size());//获取集合中元素的个数
        list.addAll(list1);//将集合中的元素全部添加到自己中
        System.out.println(list);
        list.remove("wbt");//移除了元素，并且是靠前的元素（从下标0开始找，找到了就停止，）
        System.out.println(list);
        ArrayList<String> list2 = new ArrayList<String>();
        list2.add("wgx");
        list.removeAll(list2);//移除了后面的元素，并且重复了也移除了
       /* System.out.println(list);
        list.ensureCapacity(7);//*/
        //System.out.println(list);
        Object clone = list.clone();//克隆之后发现是Object类型
        System.out.println(clone);
        System.out.println(list.indexOf("wbt"));//获得该元素下标
        list.add("ssn");
        list.add("zmy");
        list.add("ssn");
        System.out.println(list);
        System.out.println(list.lastIndexOf("ssn"));//获得最后一个此元素的下标
        //list.retainAll(list1);除了list1中包含的元素，其余都删除
        //System.out.println(list);
        //list.removeIf("zmy","ssn","wh","wbt");
        //list.ensureCapacity(7);
    }
}

LinkedList Api的调用

public class LinkedListDemo {
    public static void main(String[] args) {
        final LinkedList<String> strings = new LinkedList<>();
        strings.add("wgx");
        strings.add("wh");
        strings.add("wbt");
        strings.add("zmy");
        strings.add("ssn");//添加元素，按照插入的顺序保存，添加到最后
        System.out.println(strings);
        strings.add(1, "wbt");//在指定位置插入元素，直接更改指针指向
        System.out.println(strings);
        strings.removeFirst();//移除第一个元素
        System.out.println(strings);
        strings.remove("wh");//移除对应元素
        System.out.println(strings);
        strings.remove(0);//移除指定位置的元素
        System.out.println(strings);
        System.out.println(strings.peek());//获取第一个元素
        System.out.println(strings);
        strings.addFirst("wgx");//在最前面添加元素
        System.out.println(strings);
        strings.addLast("wh");//在最后面添加元素，和add一样使用的都是linkLast()
        System.out.println(strings);
        System.out.println(strings.get(2));//获取指定下标元素
        strings.offer("zmy");//在最后添加元素，使用的也是linkLast();方法
        System.out.println(strings);
        strings.add("wh");
        System.out.println(strings);
        strings.removeLastOccurrence("wh");//移除相同的此元素中，最后一个该元素
        System.out.println(strings);
        strings.poll();//移除第一个元素
        System.out.println(strings);
        strings.pollFirst();//移除第一个元素
        strings.pollLast();//移除最后一个元素
        System.out.println(strings);
        System.out.println(strings.peekFirst());//读取第一个元素
        System.out.println(strings.peekLast());//读取最后一个元素
        System.out.println(strings);
        strings.add("wh");
        strings.add("wh");
        System.out.println(strings.indexOf("wh"));
    }
}

List集合的特点：可以将元素维护在特定的序列中，并且按照它的存入的顺序进行存放，可以在中间插入或者删除元素，由两种类型的List，ArrayList和LinkedList。
ArrayList开辟一整片空间存入元素，按照插入的顺序保存元素，对进行随机访问元素较快
LinkedList类型，链表形式，按照插入顺序保存元素，通过指针的形式指向下一个元素，对插入和删除操作比较方便
Arrays.asList()方法返回的是new Arraylist（），首先将其转换成数组，之后调用System.arrayCopy方法，将其创建出来，由于他底层使用数组实现的，可以使用SystemCopy进行备份，但是无法对其进行修改
Set：首先，Set较于Collection接口，没有多的方法，并且Set的底层是由Map实现的。然后Set并不保存重复的元素

public class HashSetDemo {
    public static void main(String[] args) {
        final HashSet<String> strings = new HashSet<>();
        strings.add("wuhu");
        strings.add("dag");//添加元素
        System.out.println(strings.contains("dag"));//是否包含后面的元素
        strings.remove("dag");//移除该元素
        System.out.println(strings);
        //System.out.println(strings.spliterator());
        System.out.println(strings.size());//集合中元素的个数
        final Object clone = strings.clone();
        System.out.println(clone);//克隆，Object类型
    }
}

public class TreeSetDemo {
    public static void main(String[] args) {
        final TreeSet<Integer> integerTreeSet = new TreeSet<>();
        integerTreeSet.add(1);
        integerTreeSet.add(2);
        integerTreeSet.add(3);
        integerTreeSet.add(4);//添加元素
        System.out.println(integerTreeSet);
        System.out.println(integerTreeSet.ceiling(0));//获取它的元素，如果没有这个元素
                                                        //就会返回大于这个元素的最小的元素
        System.out.println(integerTreeSet);
        System.out.println(integerTreeSet.contains(4));//是否包含这个元素
        System.out.println(integerTreeSet.first());//读取第一个元素
        System.out.println(integerTreeSet.floor(100));//获取它的元素，如果没有这个元素
                                                        //就会返回小于这个元素的最大的元素
        System.out.println(integerTreeSet.higher(0));//同ceiling方法
        System.out.println(integerTreeSet.last());//获取最后一个元素
        integerTreeSet.pollFirst();//移除第一个元素
        System.out.println(integerTreeSet);
        integerTreeSet.pollLast();//移除最后一个元素
        System.out.println(integerTreeSet);
    }
}

填充容器

class StringAddress{
    private String s;
    public StringAddress(String s) {
        this.s = s;
    }
    @Override
    public String toString() {
        return super.toString() + "  " + s;
    }
}
public class FillingLists {
    public static void main(String[] args) {
        final ArrayList<StringAddress> list = new ArrayList<>(
                Collections.nCopies(4, new StringAddress("Hello")));//底层是将其转换成为数组
        System.out.println(list);
        Collections.fill(list,new StringAddress("world"));//只可以对已经存在的元素进行修改
        System.out.println(list);
    }
}

Generator的解决方案

所有的Collection的子类型都有一个接受另外一个Collection对象的构造器

public class CollectionData<T> extends ArrayList<T> {
    public CollectionData(Generator<T> gen, int quantity){
        for (int i = 0; i < quantity; i++) {
            add(gen.next());
        }
    }
    public static <T> CollectionData<T> list(Generator<T> gen,int quantity) {
        return new CollectionData<T>(gen, quantity);
    }
}

class Goverment implements Generator<String>{
    String[] s = ("strange women lying in ponds distributing swords is no " +
            "basis for a  System of").split(" ");
    private int index;
    @Override
    public String next() {
        return s[index++];
    }
}
public class CollectionDataTest {
    public static void main(String[] args) {
        final CollectionData<String> strings = new CollectionData<>(new Goverment(), 15);
        final Set<String> set = new LinkedHashSet<>(strings);
        //通过接受的Collection对象中的元素来填充新的容器
        set.addAll(CollectionData.list(new Goverment(), 15));
        System.out.println(set);
    }
}

Map生成器

public class Pair<K,V> {
  public final K key;
  public final V value;
  public Pair(K k, V v) {
    key = k;
    value = v;  //就是为了生成一对键值对，将他们定义成final类型，这样就可以让他们只读不能修改
  }
}

public class MapData<K, V> extends LinkedHashMap<K, V> {
    public MapData(Generator<Pair<K, V>> gen, int quantity) {
        for (int i = 0; i < quantity; i++) {
            Pair<K, V> p = gen.next();
            put(p.key, p.value);//生成键值对
        }
    }
    public MapData(Generator<K> genK, Generator<V> genV,
                   int quantity) {
        for (int i = 0; i < quantity; i++) {
            put(genK.next(), genV.next());
        }
    }
    // 生成键
    public MapData(Generator<K> genK, V value, int quantity) {
        for (int i = 0; i < quantity; i++) {
            put(genK.next(), value);
        }
    }
    // 生成值
    public MapData(Iterable<K> genK, Generator<V> genV) {
        for (K key : genK) {
            put(key, genV.next());
        }
    }
    //
    public MapData(Iterable<K> genK, V value) {
        for (K key : genK) {
            put(key, value);
        }
    }
    public static <K, V> MapData<K, V>
    map(Generator<Pair<K, V>> gen, int quantity) {
        return new MapData<K, V>(gen, quantity);
    }
    public static <K, V> MapData<K, V>
    map(Generator<K> genK, Generator<V> genV, int quantity) {
        return new MapData<K, V>(genK, genV, quantity);
    }
    public static <K, V> MapData<K, V>
    map(Generator<K> genK, V value, int quantity) {
        return new MapData<K, V>(genK, value, quantity);
    }
    public static <K, V> MapData<K, V>
    map(Iterable<K> genK, Generator<V> genV) {
        return new MapData<K, V>(genK, genV);
    }
    public static <K, V> MapData<K, V>
    map(Iterable<K> genK, V value) {
        return new MapData<K, V>(genK, value);
    }
}

class Letters implements Generator<Pair<Integer, String>>,
        Iterable<Integer> {
    private int size = 9;
    private int number = 1;
    private char letter = 'A';
    public Pair<Integer, String> next() {
        return new Pair<Integer, String>(
                number++, "" + letter++);  //生成键值对
    }
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            public Integer next() {
                return number++;                //对键进行迭代
            }
            public boolean hasNext() {
                return number < size;
            }
            public void remove() {
                throw new UnsupportedOperationException();
            }//执行此操作就会报错
        };
    }
}
public class MapDataTest {
    public static void main(String[] args) {
        // 生成键，值是固定的
        print(MapData.map(new Letters(), 11));
        //将字符作为键，将随机产生字符串作为值
        print(MapData.map(new CountingGenerator.Character(),
                new RandomGenerator.String(3), 8));
        // 将字符作为键，值是固定的
        print(MapData.map(new CountingGenerator.Character(),
                "Value", 6));
        //对它的键迭代并且随机产生字符串最为值
        print(MapData.map(new Letters(),
                new RandomGenerator.String(3)));
        // 对键进行迭代，并且值是不变的
        print(MapData.map(new Letters(), "Pop"));//对应上方代码大方法
    }
}

使用一个abstract类

Collection的功能方法

public class CollectionMethods {
    public static void main(String[] args) {
        Collection<String> c = new ArrayList<String>();
        c.addAll(net.mindview.util.Countries.names(6));
        c.add("ten");
        c.add("eleven");//添加元素
        print(c);
        Object[] array = c.toArray();//转换称为数组
        String[] str = c.toArray(new String[0]);
        print("Collections.max(c) = " + Collections.max(c));//找出最大的元素
        print("Collections.min(c) = " + Collections.min(c));//找到最小的元素
        Collection<String> c2 = new ArrayList<String>();
        c2.addAll(net.mindview.util.Countries.names(6));
        c.addAll(c2);
        print(c);//添加后面的集合中所有的元素
        c.remove(net.mindview.util.Countries.DATA[0][0]);
        print(c);
        c.remove(net.mindview.util.Countries.DATA[1][0]);
        print(c);
        c.removeAll(c2);//移除后面集合中所有的元素
        print(c);
        c.addAll(c2);
        print(c);
// 是否包含这个元素
        String val = net.mindview.util.Countries.DATA[3][0];
        print("c.contains(" + val + ") = " + c.contains(val));
        //是否包含这个集合
        print("c.containsAll(c2) = " + c.containsAll(c2));
        Collection<String> c3 = ((List<String>) c).subList(3, 5);
        //除了后面的集合中包含的元素，其余都删除
        c2.retainAll(c3);
        print(c2);
//   删除后面集合中包含的元素
        c2.removeAll(c3);
        print("c2.isEmpty() = " + c2.isEmpty());//判断是否为空
        c = new ArrayList<String>();
        c.addAll(Countries.names(6));
        print(c);
        c.clear(); //清楚所有的元素
        print("after c.clear():" + c);
    }
}

可选操作

执行某些方法就会抛出异常

public class Unsupported {
  static void test(String msg, List<String> list) {
    System.out.println("--- " + msg + " ---");
    Collection<String> c = list;
    Collection<String> subList = list.subList(1,8);
    Collection<String> c2 = new ArrayList<String>(subList);
    try { c.retainAll(c2); } catch(Exception e) {
      System.out.println("retainAll(): " + e);
    }
    try { c.removeAll(c2); } catch(Exception e) {
      System.out.println("removeAll(): " + e);
    }
    try { c.clear(); } catch(Exception e) {
      System.out.println("clear(): " + e);
    }
    try { c.add("X"); } catch(Exception e) {
      System.out.println("add(): " + e);
    }
    try { c.addAll(c2); } catch(Exception e) {
      System.out.println("addAll(): " + e);
    }
    try { c.remove("C"); } catch(Exception e) {
      System.out.println("remove(): " + e);
    }
    try {
      list.set(0, "X");
    } catch(Exception e) {
      System.out.println("List.set(): " + e);
    }
  }
  public static void main(String[] args) {
    List<String> list =
      Arrays.asList("A B C D E F G H I J K L".split(" "));
    test("Modifiable Copy", new ArrayList<String>(list));  //可以执行上述的方法，所以不会报错
    test("Arrays.asList()", list);//因为是asList形式，仅支持读和此修改的操作，改变大小的操作
                                      //都不能够执行
    test("unmodifiableList()",
      Collections.unmodifiableList(
        new ArrayList<String>(list)));//虽然是ArrayList形式，但是由unmodifiablelist包裹，走的是
                            //UnmodifiableList(List<? extends E> list)这个内部类
  }
}

Set和存储顺序

set：不保存重复元素，和Collection接口中的方法一样
HashSet：根据它的hashcode保存元素，查找非常的快速
TreeSet：底层是树结构，可以对添加进来的元素进行排序
LinkedhashSet：拥有hashset的查询速度，按照插入的顺序保存元素
set的底层是由map实现的

class SetType {
  int i;
  public SetType(int n) { i = n; }
  public boolean equals(Object o) {
    return o instanceof SetType && (i == ((SetType)o).i);
  }
//  public int hashCode(){
//    return i;
//  }
  public String toString() { return Integer.toString(i); }
}
class HashType extends SetType {
  public HashType(int n) { super(n); }
  public int hashCode() { return i; }
}
class TreeType extends SetType
implements Comparable<TreeType> {
  public TreeType(int n) { super(n); }
  public int compareTo(TreeType arg) {
    return (Integer.compare(arg.i, i));
  }
  /*public int hashCode(){
    return i;
  }*/
}
public class TypesForSets {
  static <T> Set<T> fill(Set<T> set, Class<T> type) {
    try {
      for(int i = 0; i < 10; i++)
          set.add(//获取传进来的Class对象的构造器
            type.getConstructor(int.class).newInstance(i));//根据反射来创建实例
    } catch(Exception e) {
      throw new RuntimeException(e);
    }
    return set;
  }
  static <T> void test(Set<T> set, Class<T> type) {
    fill(set, type);
    fill(set, type);
    fill(set, type);
    System.out.println(set);
  }
  public static void main(String[] args) {
    test(new HashSet<HashType>(), HashType.class);//由于HashType这个类重写了hashcode，就算执行100次，也只会输出10个元素
    test(new LinkedHashSet<HashType>(), HashType.class);
    test(new TreeSet<TreeType>(), TreeType.class);
    test(new HashSet<SetType>(), SetType.class);//以下的类中没有重写hashcode方法，所以会输出30个元素
    test(new HashSet<TreeType>(), TreeType.class);
    test(new LinkedHashSet<SetType>(), SetType.class);
    test(new LinkedHashSet<TreeType>(), TreeType.class);
    try {
      test(new TreeSet<SetType>(), SetType.class);
    } catch(Exception e) {
      System.out.println(e.getMessage());
    }
    try {
      test(new TreeSet<HashType>(), HashType.class);
    } catch(Exception e) {
      System.out.println(e.getMessage());
    }
  }
}

SortedSet

Sorted中的元素可以处于排序状态

public class SortedSetDemo {
    public static void main(String[] args) {
        SortedSet<String> sortedSet = new TreeSet<String>();
        Collections.addAll(sortedSet,
                "one two three four five six seven eight"
                        .split(" "));
        print(sortedSet); //根据asci码对其进行排序
        String low = sortedSet.first();//获取第一个元素
        String high = sortedSet.last();//获取最后的一个元素
        //print(low);
        //print(high);
        Iterator<String> it = sortedSet.iterator();
        for (int i = 0; i <= 6; i++) {
            if (i == 3) low = it.next();
            if (i == 6) high = it.next();
            else it.next();
        }
        print(low);
        print(high);
    print(sortedSet.subSet(low, high));//获取视图，左闭右开
    print(sortedSet.headSet(high));//获取high之前的元素
    print(sortedSet.tailSet(low));//获取low之后的元素
    }
}

队列

LinkedList和PriorityQueue 他们的差异在于排序行为而不是性能

public class QueueBehavior {
    private static int count = 10;
    static <T> void test(Queue<T> queue, Generator<T> gen) {
        for (int i = 0; i < 10; i++) {
            queue.offer(gen.next());
        }
        while (queue.peek() != null) {
            System.out.print(queue.remove() + " ");
        }
        System.out.println();
    }
    static class Gen implements Generator<String> {
        String[] s = "one two three four five six seven eight nine ten".split(" ");
        int i;
        @Override
        public String next() {
            return s[i++];
        }
    }
    public static void main(String[] args) {
        test(new LinkedList<>(), new Gen());
        test(new PriorityQueue<>(), new Gen());//根据元素的Ascii码的元素顺序排序
        test(new ArrayBlockingQueue<String>(count), new Gen());//使用固定的容量和默认的访问策略创建一个队列
        test(new ConcurrentLinkedQueue<>(), new Gen());
        test(new LinkedBlockingQueue<>(), new Gen());//创建一个容量为Integer.Max_VALUE的集合
        test(new PriorityBlockingQueue<>(),new Gen());
    }
}

优先级队列

列表中每个对象都包含一个字符串和一个主要的以及次要的优先级值，该列表的排列顺序也是通过实现comparable而进行控制的

public class ToDoList extends PriorityQueue<ToDoList.ToDoItem> {
    static class ToDoItem implements Comparable<ToDoItem> {
        private char primary;
        private int secondary;
        private String item;
        public ToDoItem(String td, char pri,int sec) {
            primary = pri;
            secondary = sec;
            item = td;
        }
        @Override
        public int compareTo(ToDoItem arg) {
            if (primary > arg.primary) {//先根据char来判断它的顺序
                return +1;
            }
            if (primary == arg.primary) {
                //如果字符相等，就根据字符后面的数字来判断顺序
                if (secondary > arg.secondary) {
                    return +1;
                } else if (secondary == arg.secondary) {
                    return 0;
                }
            }
            return -1;
        }
        @Override
        public String toString() {
            return Character.toString(primary) + secondary + ": " + item;
        }
    }
    public void add(String td, char pri, int sec) {
        super.add(new ToDoItem(td, pri, sec));
    }
    public static void main(String[] args) {
        ToDoList toDoList = new ToDoList();
        toDoList.add("Empty trash", 'C', 4);
        toDoList.add("Feed dog", 'A', 2);
        toDoList.add("Feed bird", 'B', 7);
        toDoList.add("Mow lawn", 'C', 3);
        toDoList.add("Water lawn", 'A', 1);
        toDoList.add("Feed cat", 'B', 1);
        while (!toDoList.isEmpty()) {
            System.out.println(toDoList.remove());
        }
    }
}

双向队列

双向队列（双端队列）就像是一个队列，但是可以在任何一端添加或者移除元素。LinkedList无法实现这样的接口，可以使用组合来创建一个Deque类（见工具类）

public class DequeTest {
    static void fillTest(Deque<Integer> deque) {
        for (int i = 20; i < 27; i++) {
            deque.addFirst(i);//加到前面
        }
        for (int i = 50; i < 55; i++) {
            deque.addLast(i);//加到后面
        }
    }
    public static void main(String[] args) {
        Deque<Integer> di = new Deque<>();
        fillTest(di);
        System.out.println(di);
        while (di.size() != 0) {
            System.out.print(di.removeLast()+"   ");//从后面开始移除
        }
    }
}

理解Map

映射表（关联数组）的基本思想是它维护的是键-值对关联，因此可以使用键来查找值
利用二位数组来模拟MapAPI的实现

public class AssociativeArray<K, V> {
    private Object[][] pairs;
    private int index;
    public AssociativeArray(int length) {
        pairs = new Object[length][2];
    }
    public void put(K key, V value) {
        if (index >= pairs.length) {
            throw new ArrayIndexOutOfBoundsException();
        }
        pairs[index++] = new Object[]{key, value};
    }
    public V get(K key) {
        for (int i = 0; i < index; i++) {
            if (key.equals(pairs[i][0])) {//如果和key相等的话，就返回它的value
                return (V) pairs[i][1];
            }
        }
        return null;
    }
    @Override
    public String toString() {
        StringBuilder result = new StringBuilder();//拼接
        for (int i = 0; i < index; i++) {
            result.append(pairs[i][0].toString());
            result.append(": ");
            result.append(pairs[i][1].toString());
            if (i < index - 1) {
                result.append("\n");
            }
        }
        return result.toString();
    }
    public static void main(String[] args) {
        AssociativeArray<String, String> map = new AssociativeArray<>(6);
        map.put("sky", "blue");
        map.put("grass", "green");
        map.put("ocean", "dancing");
        map.put("tree", "tall");
        map.put("earth", "brown");
        map.put("sun", "warm");
        try {
            map.put("extra", "object");
        } catch (ArrayIndexOutOfBoundsException e) {
            System.out.println("Too many objects");
        }
        System.out.println(map);
        System.out.println(map.get("ocean"));
    }
}

性能

性能是映射表中的一个很重要的问题，当在get（）中使用线性搜索的时候，执行速度会变得相当的慢，所以HashMap使用了特殊的值，称作散列码，来取代对键的缓慢搜索，散列码是“相对唯一的”用以代表对象的int值

解决Hash冲突：一开始的容量是16，当存放的元素为16*0.75个时，就会扩容成为它的两倍
Map中键的的要求和Set中元素的要求是一样的，任何的键都必须具有一个equals方法，如果键被用于散列Map，那么它还必须具有恰当的hashCode方法，如果键被用于TreeMap，那么它必须实现Comparable

public class Maps {
    public static void printKey(Map<Integer, String> map) {
        System.out.print("Size = " + map.size() + ". ");
        System.out.print("Keys : ");
        System.out.println(map.keySet());//返回由Map键组成的Set集合
    }
    public static void test(Map<Integer, String> map) {
        System.out.println(map.getClass().getSimpleName());
        map.putAll(new CountingMapData(25));
        map.putAll(new CountingMapData(25));
        printKey(map);
        System.out.println("Values" + map.values());
        System.out.println(map);
        System.out.println("map.containsKey : " + map.containsKey(11));
        System.out.println("map.get(11) : " + map.get(11));
        System.out.println("map.containsValue(\"F0\") : " + map.containsValue("F0"));
        Integer key = map.keySet().iterator().next();
        System.out.println("First Key in map: " + key);
        map.remove(key);
        printKey(map);
        map.clear();
        System.out.println("map.isEmpty: " + map.isEmpty());
        map.putAll(new CountingMapData(25));
        map.keySet().removeAll(map.keySet());
        System.out.println("map.isEmpty: " + map.isEmpty());
    }
    public static void main(String[] args) {
        test(new HashMap<>());
    }
}

SortedMap

可以确保键可以处于排序状态

public class SortedMapDemo {
    public static void main(String[] args) {
        TreeMap<Integer, String> sortedMap = new TreeMap<>(new CountingMapData(25));
        System.out.println(sortedMap);
        Integer low = sortedMap.firstKey();
        Integer high = sortedMap.lastKey();
        System.out.println(low);
        System.out.println(high);
        Iterator<Integer> it = sortedMap.keySet().iterator();
        for (int i = 0; i <= 6; i++) {
            if (i == 3) {
                low = it.next();
            }
            if (i == 6) {
                high = it.next();
            } else {
                it.next();
            }
        }
        System.out.println(low);
        System.out.println(high);
        System.out.println(sortedMap.subMap(low, high));
        System.out.println(sortedMap.headMap(high));
        System.out.println(sortedMap.tailMap(low));
    }
}

散列和散列码

public class Groundhog {
    protected int number;
    public Groundhog(int number) {
        this.number = number;
    }
    @Override
    public String toString() {
        return "Ground# " + number;
    }
}
public class Prediction {
    private static Random rand = new Random(47);
    private boolean shadow = rand.nextDouble() > 0.5;
    @Override
    public String toString() {
        if (shadow){
            return "Six more weeks of winter";
        }
        else{
            return "Early spring";
        }
    }
}
public class SpringDetector {
    public static <T extends Groundhog> void detectSpring(Class<T> type) throws Exception {
        Constructor<T> ghog = type.getConstructor(int.class);
        final Map<Groundhog, Prediction> map = new HashMap<>();
        for (int i = 0; i < 10; i++) {
            map.put(ghog.newInstance(i), new Prediction());
        }
        System.out.println("map: " + map);
        Groundhog gh = ghog.newInstance(3);
        //虽然像构造器中传的是3，但是和map比较的时候用的是Object的equals，比较的是地址
        //所以它不在map中，所以并不能根据它来当作key来取出来value
        System.out.println("Looking up prediction for " + gh);
        if (map.containsKey(gh)) {
            System.out.println(map.get(gh));
        } else {
            System.out.println("Key not Found" + gh);
        }
    }
    public static void main(String[] args) throws Exception {
        detectSpring(Groundhog.class);
    }
}

如果想让gh可以取出在map中的value的话，必须同时重写hashcode和equals方法

public class Groundhog2 extends Groundhog{
    public Groundhog2(int n) {
        super(n);
    }
    @Override
    public int hashCode() {
        return number;
    }
    @Override
    public boolean equals(Object o) {
        return o instanceof Groundhog2 && (number == ((Groundhog2) o).number);
    }
}
public class SpringDetector2 {
    public static void main(String[] args) throws Exception {
        SpringDetector.detectSpring(Groundhog2.class);
    }
}

hash（）用于计算在hash表中的位置，然后再使用equals判断他俩是否相等，所以如果想让他俩相等的话都需要重写

为速度而散列

散列的价值在于速度，散列使得查询得以快速进行。
散列将键存在某处，以便可以很快的找到，存储一组元素最快的数据结构式数组，所以使用它来表示键的信息。（保存的是键的信息，而不是键本身）
数组并不保存键本身，而是通过键对象生成一个数字，将其作为数组的下标，这个数组就是散列码
因为数组的容量是固定的，所以不同的键可以产生相同的下标，但是可能会有冲突，因此数组多大并不重要，任何键总能在数组中找到它的位置
通常，冲突是由外部连接进行处理的，数组并不直接保存值，而是保存值的list，然后对list中的值使用equals方式进行线性的查询

public class SimpleHashMap<K, V> extends AbstractMap<K, V> {
    static final int SIZE = 997;
    @SuppressWarnings("unchecked")
    LinkedList<MapEntry<K, V>>[] buckets =
            new LinkedList[SIZE];
    public V put(K key, V value) {
        V oldValue = null;
        //计算数组下标
        int index = Math.abs(key.hashCode()) % SIZE;
        //判断数组下标处链表是否初始化
        if (buckets[index] == null)
            //初始化
            buckets[index] = new LinkedList<>();
        //持有数组下标处链表的引用
        LinkedList<MapEntry<K, V>> bucket = buckets[index];//
        //链表将要保存或覆盖的Entry
        MapEntry<K, V> pair = new MapEntry<K, V>(key, value);
        boolean found = false;
        //迭代数组下标处的链表
        ListIterator<MapEntry<K, V>> it = bucket.listIterator();
        while (it.hasNext()) {
            MapEntry<K, V> iPair = it.next();
            //判断是否已经放入容器中 包含则覆盖
            if (iPair.getKey().equals(key)) {
                oldValue = iPair.getValue();
                it.set(pair);
                found = true;
                break;
            }
        }
        //不包含放入链表尾端
        if (!found)
            buckets[index].add(pair);
        return oldValue;
    }
    public V get(Object key) {
        //根据key的哈希值计算桶下标
        int index = Math.abs(key.hashCode()) % SIZE;
        if (buckets[index] == null) return null;
        for (MapEntry<K, V> iPair : buckets[index])
            //如果包含，返回它的值
            if (iPair.getKey().equals(key))
                return iPair.getValue();
        return null;
    }
    public Set<Entry<K, V>> entrySet() {
        Set<Entry<K, V>> set = new HashSet<Entry<K, V>>();
        for (LinkedList<MapEntry<K, V>> bucket : buckets) {
            //对链表进行遍历
            if (bucket == null) continue;//如果为空继续下一次寻找
            for (MapEntry<K, V> mpair : bucket)
                set.add(mpair);
        }
        return set;
    }
    public static void main(String[] args) {
        SimpleHashMap<String, String> m =
                new SimpleHashMap<String, String>();
        m.putAll(Countries.capitals(25));
        System.out.println(m);
        System.out.println(m.get("ERITREA"));
        System.out.println(m.entrySet());
    }
}

覆盖hashcode（）

散列码不必是独一无二的，应该关注它的速度，而不是唯一性，但是使用hashCode（）和equals（），必须能完全确定对象的身份