Collections.shuffle()源码分析

Collections.shuffle()源码分析Java.util.Collections类下有一个静态的shuffle()方法,如下:1)staticvoidshuffle(List<?>list)使用默认随机源对列表进行置

大家好,又见面了,我是你们的朋友全栈君。

Java.util.Collections类下有一个静态的shuffle()方法,如下:

  1)static void shuffle(List<?> list)  使用默认随机源对列表进行置换,所有置换发生的可能性都是大致相等的。

  2)static void shuffle(List<?> list, Random rand) 使用指定的随机源对指定列表进行置换,所有置换发生的可能性都是大致相等的,假定随机源是公平的。

源码展示:

public class Collections {
    private static Random r;
    private static final int SHUFFLE_THRESHOLD = 5;
    
    public static void shuffle(List<?> list) {
        if (r == null) {
            r = new Random();
        }
        shuffle(list, r);
    }
    
    public static void shuffle(List<?> list, Random rnd) {
        int size = list.size();
        if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
            for (int i = size; i > 1; i--)
                swap(list, i - 1, rnd.nextInt(i));
        } else {
            Object arr[] = list.toArray();

            // Shuffle array
            for (int i = size; i > 1; i--)
                swap(arr, i - 1, rnd.nextInt(i));

            // Dump array back into list
            ListIterator it = list.listIterator();
            for (int i = 0; i < arr.length; i++) {
                it.next();
                it.set(arr[i]);
            }
        }
    }
    
    public static void swap(List<?> list, int i, int j) {
        final List l = list;
        l.set(i, l.set(j, l.get(i)));
    }
    
    private static void swap(Object[] arr, int i, int j) {
        Object tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    
}

基本应用(打乱一个int数组):

public class ShuffleTest {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < 10; i++)
            list.add(new Integer(i));
        System.out.println("打乱前:");
        System.out.println(list);
 
        for (int i = 0; i < 5; i++) {
            System.out.println("第" + i + "次打乱:");
            Collections.shuffle(list);
            System.out.println(list);
        }
    }
}

经典应用(洗牌):

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class CollectionsShuffle {
    public static void main(String[] args) {
        List<Card> cards = new ArrayList<Card>();
        // 生成一副牌
        for (int rank = Card.THREE; rank <= Card.DEUCE; rank++) {
            cards.add(new Card(Card.DIAMOND, rank));
            cards.add(new Card(Card.CLUB, rank));
            cards.add(new Card(Card.HEART, rank));
            cards.add(new Card(Card.SPADE, rank));
        }
        cards.add(new Card(Card.JOKER, Card.BLACK));
        cards.add(new Card(Card.JOKER, Card.COLOR));
        System.out.println(cards.toString());
        /*
         * [方块3, 梅花3, 红桃3, 黑桃3, 方块4, 梅花4, 红桃4, 黑桃4, 方块5, 梅花5, 红桃5, 黑桃5, 方块6,
         * 梅花6, 红桃6, 黑桃6, 方块7, 梅花7, 红桃7, 黑桃7, 方块8, 梅花8, 红桃8, 黑桃8, 方块9, 梅花9, 红桃9,
         * 黑桃9, 方块10, 梅花10, 红桃10, 黑桃10, 方块J, 梅花J, 红桃J, 黑桃J, 方块Q, 梅花Q, 红桃Q, 黑桃Q,
         * 方块K, 梅花K, 红桃K, 黑桃K, 方块A, 梅花A, 红桃A, 黑桃A, 方块2, 梅花2, 红桃2, 黑桃2, 小王, 大王]
         */
        // 经典洗牌算法
        Random random = new Random();
        for (int i = cards.size(); i > 1; i--) {
            int m = random.nextInt(i);
            swap(cards, i - 1, m);
        }
        System.out.println(cards.toString());
        /*
         * [黑桃7, 黑桃A, 梅花A, 红桃9, 梅花4, 红桃K, 方块5, 梅花7, 梅花6, 方块A, 黑桃Q, 梅花5, 红桃10,
         * 梅花Q, 梅花J, 方块J, 梅花K, 方块8, 方块6, 方块10, 红桃7, 方块K, 红桃6, 黑桃2, 黑桃K, 梅花10,
         * 红桃8, 方块Q, 红桃Q, 大王, 梅花3, 梅花2, 方块7, 方块9, 方块4, 红桃3, 梅花9, 红桃J, 黑桃8, 红桃2,
         * 黑桃6, 红桃A, 黑桃9, 黑桃4, 黑桃J, 黑桃10, 小王, 黑桃3, 黑桃5, 红桃5, 红桃4, 方块2, 方块3, 梅花8]
         */

    }

    public static void swap(List<?> list, int i, int j) {
        final List l = list;
        l.set(i, l.set(j, l.get(i)));
    }
}

class Card {

    public static final int DIAMOND = 0; // 方块(钻石)
    public final static int CLUB = 1; // 梅花
    public static final int HEART = 2; // 红桃(红心)
    public static final int SPADE = 3; // 黑桃(花锄)
    public static final int JOKER = 4; //

    public final static int THREE = 0;
    public final static int FOUR = 1;
    public final static int FIVE = 2;
    public final static int SIX = 3;
    public final static int SEVEN = 4;
    public final static int EIGHT = 5;
    public final static int NINE = 6;
    public final static int TEN = 7;
    public final static int JACK = 8;// J
    public final static int QUEEN = 9;// Q
    public final static int KING = 10;// K
    public final static int ACE = 11;// A
    public final static int DEUCE = 12; // 2
    public final static int BLACK = 13; // 小王
    public final static int COLOR = 14;// 大王

    /** 花色 0代表方块, 1代表梅花, 2代表红桃, 3代表黑桃,4:王 */
    private int suit;
    /** 点数 规定: 0代表3, 1代表4, 2代表5,... */
    private int rank;

    public Card() {
    }

    public Card(int suit, int rank) {
        // this.rank = rank;
        // this.suit = suit;
        setRank(rank);
        setSuit(suit);
    }

    public int getSuit() {
        return suit;
    }

    public void setSuit(int suit) {
        if (suit < DIAMOND || suit > JOKER)
            throw new RuntimeException("花色超过范围!");
        this.suit = suit;
    }

    public int getRank() {
        return rank;
    }

    public void setRank(int rank) {
        if (rank < THREE || rank > COLOR) {
            throw new RuntimeException("点数超过范围!");
        }
        this.rank = rank;
    }

    private static final String[] RANK_NAMES = { "3", "4", "5", "6", "7", "8",
            "9", "10", "J", "Q", "K", "A", "2", "小王", "大王" };
    private static final String[] SUIT_NAMES = { "方块", "梅花", "红桃", "黑桃", "" };

    // 覆盖Object 类的toStirng() 方法. 实现对象的文本描述
    public String toString() {
        return SUIT_NAMES[suit] + RANK_NAMES[rank];
    }

    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (this == obj) {
            return true;
        }
        if (obj instanceof Card) {
            Card other = (Card) obj;
            return this.rank == other.rank && this.suit == other.suit;
        }
        return false;
    }

    public int hashCode() {
        // return suit*100+rank;
        // suit=3= 00000000 00000000 00000000 00000011
        // rank=10=00000000 00000000 00000000 00000011
        // suit<<16=00000000 00000011 00000000 00000000
        // 00000000 00000011 00000000 00000011
        return (suit << 16) + rank;// (x<<16)+y
    }
}

注意:如果给定一个整型数组,用Arrays.asList()方法将其转化为一个集合类,有两种途径:

  1)用List<Integer> list=ArrayList(Arrays.asList(ia)),用shuffle()打乱不会改变底层数组的顺序。

  2)用List<Integer> list=Arrays.aslist(ia),然后用shuffle()打乱会改变底层数组的顺序。代码例子如下:

public class Modify {  
    public static void main(String[] args){  
        Random rand=new Random(47);  
        Integer[] ia={0,1,2,3,4,5,6,7,8,9};  
        List<Integer> list=new ArrayList<Integer>(Arrays.asList(ia));  
        System.out.println("Before shufflig: "+list);  
        Collections.shuffle(list,rand);  
        System.out.println("After shuffling: "+list);  
        System.out.println("array: "+Arrays.toString(ia));  
        List<Integer> list1=Arrays.asList(ia);  
        System.out.println("Before shuffling: "+list1);  
        Collections.shuffle(list1,rand);  
        System.out.println("After shuffling: "+list1);  
        System.out.println("array: "+Arrays.toString(ia));  
          
    }  
}  

结果如下:

    Before shufflig: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]  
    After shuffling: [3, 5, 2, 0, 7, 6, 1, 4, 9, 8]  
    array: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]  
    Before shuffling: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]  
    After shuffling: [8, 0, 5, 2, 6, 1, 4, 9, 3, 7]  
    array: [8, 0, 5, 2, 6, 1, 4, 9, 3, 7]  

  在第一种情况中,Arrays.asList()的输出被传递给了ArrayList()的构造器,这将创建一个引用ia的元素的ArrayList,因此打乱这些引用不会修改该数组。 但是,如果直接使用Arrays.asList(ia)的结果, 这种打乱就会修改ia的顺序。意识到Arrays.asList()产生的List对象会使用底层数组作为其物理实现是很重要的。 只要你执行的操作 会修改这个List,并且你不想原来的数组被修改,那么你就应该在另一个容器中创建一个副本。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/155268.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Python sorted 函数

    Python sorted 函数Pythonsorted函数sorted可以对所有可迭代的对象进行排序操作,sorted方法返回的是一个新的list,而不是在原来的基础上进行的操作。从新排序列表。sorted语法:

  • vim编辑器怎么退出_退出vim编辑器

    vim编辑器怎么退出_退出vim编辑器当编辑完文件,准备退出Vi返回到shell时,可以使用以下几种方法之一。  (1)在命令模式中,连按两次大写字母Z,若当前编辑的文件曾被修改过,则Vi保存该文件后退出,返回到shell;若当前编辑的文件没被修改过,则Vi直接退出,返回到shell。  (2)在末行模式下,输入命令:wVi保存当前编辑文件,但并不退出,而是继续等待用户输入命令。在使用w命令时,可以再给编辑文件起一个新的文件名。…

  • AIC(最小信息化准则)

    AIC(最小信息化准则)AIC信息准则(即Akaikeinformationcriterion),是用来衡量统计模型拟合优良性的一个标准,是是由日本统计学家赤池弘次创立和发展的,因此也称为赤池信息量准则,它建立在熵的概念基础上,可以权衡所估计模型的复杂度和模型拟合数据的优良性。在一般情况下,AIC可以表示为:AIC=2k-2ln(L)其中:k是参数的数量,L是似然函数。假设条件是模型的误差服从独立正态分布。让n为观察…

  • php删除字符串的空格

    php删除字符串的空格php删除字符串的空格

  • MapReduce 编程不可怕,一篇文章搞定它

    MapReduce 编程不可怕,一篇文章搞定它前言本文隶属于专栏《1000个问题搞定大数据技术体系》,该专栏为笔者原创,引用请注明来源,不足和错误之处请在评论区帮忙指出,谢谢!本专栏目录结构和参考文献请见1000个问题搞定大数据技术体系正文需求:WordCount,大数据领域的HelloWorld。Mapperpackagecom.shockang.study.bigdata.mapreduce;importjava.io.IOException;importorg.apache.hadoop.io.IntWr

  • 《前端运维》一、Linux基础–03Shell基础及补充「建议收藏」

    诶诶欸?不是学Linux么?怎么要讲shell了?shell是啥?啥是shell?别急,我们先简单了解下shell是什么。Shell是一个用C语言编写的程序,它是用户使用Linux的桥梁。

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号