A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 田林 中级黑马   /  2012-9-25 22:39  /  1739 人查看  /  5 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 屈俊材 于 2012-9-26 07:54 编辑

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

评分

参与人数 1技术分 +1 收起 理由
刘芮铭 + 1 赞一个!

查看全部评分

5 个回复

正序浏览
      Set
     /   \
    /     \
HashSet  TreeSet

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

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

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


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

评分

参与人数 1技术分 +1 收起 理由
刘芮铭 + 1 赞一个!

查看全部评分

回复 使用道具 举报
各种集合底层实现
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;
  }

评分

参与人数 1技术分 +1 收起 理由
刘芮铭 + 1 赞一个!

查看全部评分

回复 使用道具 举报
集合:老毕教程上讲了大类,1,List集合和2,Set集合
List集合分为ArrayList和LinkedList:
ArrayList:底层是数组结构;
LinkedList:底层是链表结构;

set集合分为HashSet和TreeSet等,
HashSet:底层是Hash表结构;
TreeSet:底层是二叉树结构;
具体内容老毕视频上都有讲!

评分

参与人数 1技术分 +1 收起 理由
刘芮铭 + 1 赞一个!

查看全部评分

回复 使用道具 举报
有时间你学下数据结构和算法就会很清楚了。
回复 使用道具 举报
其实这些你看些书,比如《数据结构》总结下就可以了。
不用太深入,了解各自的优缺点,会使用就行了。
最好是自己写片日记总结。

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

评分

参与人数 1技术分 +1 收起 理由
刘芮铭 + 1 赞一个!

查看全部评分

回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马