study hard and make progress every day
Text has been added to my Github repository DayDayUP, welcome Star, more articles please go to: directory navigation
preface
Today I ran into a problem when I scanned LeetCode. The ArrayList couldn’t add data to it. It’s not that the data was not added, but that the data was changed. When it comes to the question of whether an ArrayList stores a value or a reference, there are many answers on the web: if it’s a primitive data type, it stores a value, and if it’s an object, it stores a reference. So what is it? Let’s find out!
The body of the
The original title is here:
39. Sum of combinations
Given an array of no duplicate elements and a target number, find all combinations of the candidates that make the numeric sum target.
The numbers in the candidates can be selected repeatedly without limit.
My initial code looks like this:
class Solution {
private List<List<Integer>> result = new ArrayList();
private ArrayList<Integer> solution = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) { backtracking(candidates,target,0); return result; } public void backtracking(int[] candidates, int residual, int start) { if (residual < 0) { return; } if (residual == 0) { result.add(solution); return; } for(inti = start; i<candidates.length; i++) { solution.add(candidates[i]); backtracking(candidates,residual-candidates[i],i); solution.remove(solution.size()-1); } } } Copy the codeCheck the List, there is no problem, very confident click run, the result is confused, there is nothing in the List
Since the output is two [], data must have been added twice in the List, that is, entered into the if statement, so the possible reason is that there is something wrong with the code, so there is no data in the solution, so let’s print it.
Modify code:
... if (residual == 0) {
System.out.println(solution.toString()); / / print solution
result.add(solution);
return; } ... Copy the codeIf you look at the console, the solution prints normally, and the result is correct
Since the solution has the correct data, the problem should be added to the List, so print it again.
Modify code:
... if (residual == 0) {
result.add(solution);
System.out.println("-- -- -- -- -- -- -- -- -- --");
for (List<Integer> integers : result) { System.out.println(integers.toString()); // Print the contents of the List } System.out.println("= = = = = = = = = ="); return; } ... Copy the code
From the printed content, the first addition is [2,2,3], no problem. But the print result of the second time is very strange, there are two [7], that is, the content I added the first time is modified. There is only one possible reason why a reference was added to the List instead of the actual value, otherwise the result would have changed. But are the references in the List really there? Let’s test that a little bit further.
First we specify the generics in ArrayList as wrapper classes for the primitive data types and a User class that we define ourselves:
public class ArrayListTest {
static class User {
private String name;
private int age;
public User(String name , int age) { this.name = name; this.age = age; } @Override public String toString(a) { return "User{" + "name='" + name + '\' ' + ", age=" + age + '} '; } } public static void main(String[] args) { ArrayList<Integer> integerArrayList = new ArrayList<>(); int testInt = 10; integerArrayList.add(testInt); testInt = 20; integerArrayList.add(testInt); System.out.println(integerArrayList.toString()); ArrayList<Double> doubleArrayList = new ArrayList<>(); double testDouble = 100.0; doubleArrayList.add(testDouble); testDouble = 200.0; doubleArrayList.add(testDouble); System.out.println(doubleArrayList.toString()); ArrayList<User> userArrayList = new ArrayList<>(); User testUser = new User("Zhang".20); userArrayList.add(testUser); testUser.age = 22; userArrayList.add(testUser); for (User user : userArrayList) { System.out.println(user.toString()); } } Copy the codeHere we try both Integer and Double, and see what happens:
As you can see, changing int and double does not affect the previous content, but changing User does. So if an ArrayList is a primitive data type, it stores values; if an ArrayList is an object, it stores references to objects rather than copies of objects. That seems to be the case, but the big question is can an ArrayList hold primitive data types? An error is reported if generics are specified as primitive data types:
Therefore, ArrayList does not have the problem of storing primitive data types. It can only store the wrapper classes of primitive data types, which means that the primitive data types are automatically boxed into an object and then stored with references. Okay, so even if I don’t store the basic data type, but I store the wrapper class, then after I change the contents inside, the Integer and Double store different values twice, and the User store the same two values. Because if the generic type is Integer or Double, it stores references to different objects instead of one, which of course would cause the previous content to change. Ideas for Java Programming says that whenever you call hashCode() on the same object, you should generate the same value. So let’s print out their hash value to see if they’re the same object. We use system.identityHashCode () to get the hash value:
... public static void main(String[] args) {
ArrayList<Integer> integerArrayList = new ArrayList<>();
int testInt = 10;
integerArrayList.add(testInt);
testInt = 20; integerArrayList.add(testInt); for (Integer integer : integerArrayList) { System.out.println(integer + ":"+ System.identityHashCode(integer)); } System.out.println(); ArrayList<Double> doubleArrayList = new ArrayList<>(); double testDouble = 100.0; doubleArrayList.add(testDouble); testDouble = 200.0; doubleArrayList.add(testDouble); for (Double aDouble : doubleArrayList) { System.out.println(aDouble + ":"+ System.identityHashCode(aDouble)); } ArrayList<User> userArrayList = new ArrayList<>(); User testUser = new User("Zhang".20); System.out.println("\nUser before modification:"); System.out.println(testUser.toString()); System.out.println(System.identityHashCode(testUser)); userArrayList.add(testUser); testUser.age = 22; System.out.println("User modified:"); System.out.println(testUser.toString()); System.out.println(System.identityHashCode(testUser)); userArrayList.add(testUser); System.out.println("ArrayList
:"
); for (User user : userArrayList) { System.out.println(user.toString()); System.out.println(System.identityHashCode(user)); } } ...Copy the codeThe printed result is as follows:
As you can see from the printed result, Integer and Double do not modify the content, but store a reference to a new object, so the wrapper class that stores the basic data type is also a reference rather than a value, while the User object can be modified to affect the previously stored content. The two users are the same.
Why can’t Integer and Double be modified? Because they are immutable, they are final, meaning that the second assignment refers to a new object, not the previous one. From the source we can see:
As you can see, the wrapper classes for basic datatypes are final, as are strings, and there is no way to modify values in the wrapper classes for basic datatypes, such as Double and Integer. When the ArrayList stores data a second time, it does not change the value of the memory address in the first reference, but instead stores a new reference.
conclusion
So far, the conclusion is that an ArrayList holds references, not values.
Some people on the Internet say that “basic data types are values, objects are references” this conclusion is wrong. So back to the original question, how do I write this? In fact, just one copy is good:
... if (residual == 0) {
result.add((List<Integer>) solution.clone());
return;
} ... Copy the code