黑马程序员技术交流社区

标题: 集合问题 [打印本页]

---

作者: 田林    时间: 2012-9-25 22:39
标题: 集合问题


集合学完了，但对集合的底层实现和排序仍有些迷茫，不知道哪位大虾能帮忙整理一下思路？重点是底层怎么实现的。小弟不胜感激！

---

作者: 杨卫腾    时间: 2012-9-25 22:50
其实这些你看些书，比如《数据结构》总结下就可以了。
不用太深入，了解各自的优缺点，会使用就行了。
最好是自己写片日记总结。

总体上 掌握 Set 和 List 集合，还有Map集合，这些是开发常用的
集合。

---

作者: 王胜炎    时间: 2012-9-25 22:51
有时间你学下数据结构和算法就会很清楚了。

---

作者: 黑马杨晨    时间: 2012-9-25 22:54
集合：老毕教程上讲了大类，1，List集合和2，Set集合
List集合分为ArrayList和LinkedList：
ArrayList：底层是数组结构；
LinkedList：底层是链表结构;

set集合分为HashSet和TreeSet等，
HashSet：底层是Hash表结构；
TreeSet：底层是二叉树结构；
具体内容老毕视频上都有讲！

---

作者: 柳彬    时间: 2012-9-25 22:55
各种集合底层实现
ArrayList: object[]
代码片段：构造方式
  public ArrayList() {
        this(10);//默认一开始构造了size为10的Object数组
  }
public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }
优缺点：读快改慢
linkedList: Entry链表 ,单向链表
private transient Entry<E> header = new Entry<E>(null, null, null);
public LinkedList() {
        header.next = header.previous = header;
}
优缺点：读慢改快

HashMap：Entry[]
          public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = new Entry[DEFAULT_INITIAL_CAPACITY];//构建Entry数组
        init();
    }
public V get(Object key) { //获取的时候从数组中读取
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }
//put方法 put的时候需要首先遍历数组的，看是否有重复的key
public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next){
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

TreeMap: 基于Entry的二叉树
        public V get(Object key) {
        Entry<K,V> p = getEntry(key);
        return (p==null ? null : p.value);
    }
put方法的部分代码块：根据比较大小决定是放在某个结点的左边还是右边，如果值相同直接覆盖。左边大右边小
    if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }


HashSet：  基于HashMap实现，因为map中的key是不能重复的
public HashSet() {
                map = new HashMap<E,Object>();
}
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
}


TreeSet：TreeMap
        public TreeSet() {
                this(new TreeMap<E,Object>());
   }
        public boolean add(E e) {
        return m.put(e, PRESENT)==null;
  }

---

作者: 程振    时间: 2012-9-25 23:10
      Set
     /   \
    /     \
HashSet  TreeSet

HashSet利用HashMap的key的唯一性来实现集合的元素唯一性，一般不对元素排序，想排序就使用TreeSet

TreeSet利用TreeMap的key的唯一性来实现集合的元素唯一性,想对集合元素排序就使用TreeSet，另外TreeMap里面还有
private void rotateLeft(Entry<K,V>) 左旋转
private void rotateRIght(Entry<K,V>) 右旋转

应该是使用的红黑树存储数据的。


集合的排序。。。这个没注意过，忘了怎么用了

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2